BOJ 5980 - Corn Maze

문제

백준 온라인 저지 - 5980번

풀이 과정

시작지점에서 목표지점에 도달하기 위한 최소 이동 횟수를 구하는 BFS 문제입니다.

여기서 주의할 점은 특정 지점간의 양방향 포탈이 존재한다는 것입니다.

각각의 포탈은 대문자 알파벳으로 제공되기 때문에 해시 테이블 을 이용해서 각 포탈의 정보를 관리합니다.

또한 중복 방문을 방지하기 위해서 visit 을 체크할 때 포탈의 위치는 중복 방문을 허용해야 한다는 점에 주의합니다.

이렇게 하지 않으면 포탈을 한번밖에 사용하지 못하는 상황이 발생하여 필요할 때 사용할 수 없기 때문입니다.

이로인해 다음과 같은 예시에서 문제가 발생할 수 있습니다.

######
#.WB##
#.####
=B@W##
######

코드

import sys
from collections import deque

N, M = list(map(int, sys.stdin.readline().split()))
board = [list(sys.stdin.readline().strip()) for _ in range(N)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def pre_processing():
    start, goal = [], []
    slides = {}

    for x in range(N):
        for y in range(M):
            if board[x][y] == '@':
                start = [x, y]
            if board[x][y] == '=':
                goal = [x, y]
            if 'A' <= board[x][y] <= 'Z':
                if board[x][y] not in slides:
                    slides[board[x][y]] = [[x, y]]
                else:
                    slides[board[x][y]].append([x, y])

    return start, goal, slides


def bfs(start, goal, slides):
    q = deque()
    visit = [[0] * M for _ in range(N)]

    q.append([*start, 0])
    visit[start[0]][start[1]] = 1

    while q:
        x, y, cost = q.popleft()

        if [x, y] == goal:
            return cost

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                if not board[nx][ny] == '#' and not visit[nx][ny]:
                    if 'A' <= board[nx][ny] <= 'Z':
                        slide = slides[board[nx][ny]]

                        if [nx, ny] == slide[0]:
                            q.append([*slide[1], cost + 1])
                        else:
                            q.append([*slide[0], cost + 1])
                    else:
                        if not visit[nx][ny]:
                            visit[nx][ny] = 1
                            q.append([nx, ny, cost + 1])


def solution():
    start, goal, slides = pre_processing()
    answer = bfs(start, goal, slides)

    return answer


print(solution())