[백준 02178] 미로 탐색 [Python]

문제

https://www.acmicpc.net/problem/2178

 

---

풀이

주어진 보드의 (0, 0)에서 (N - 1, M - 1)에 도달하기 위해 움직인 최소 횟수를 구하는 문제다.

BFS로 탐색을 진행했다.

if __name__ == '__main__':
    # Input
    N, M = map(int, input().split())
    board = [[*map(int, input().rstrip())] for _ in range(N)]

    # Solve & Output
    print(bfs(N - 1, M - 1))

큐에는 현재 위치 (x, y)를 담았으며, 따로 방문 횟수를 기록해도 되지만 주어진 board를 활용했다.

빈 공간은 1로, 이동하면서 기존 위치의 값 + 1으로 채웠다.

이미 방문한 곳은 1이 아니여야 하기 때문에 (0, 0)을 2로 시작했고,

마지막 결과에서 다시 1을 빼주는 방식으로 올바른 정답을 계산했다.

def bfs(N, M):
    queue = deque([(0, 0)])
    board[0][0] = 2
    while queue:
        x, y = queue.popleft()
        if x == N and y == M:
            return board[x][y] - 1
        for dx, dy in D:
            nx, ny = x + dx, y + dy
            if is_valid(nx, ny):
                board[nx][ny] = board[x][y] + 1
                queue.append((nx, ny))

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/02178.py