[Baekjoon] 2178 - 미로 탐색 BFS (Python)

[Baekjoon] 2178 - 미로 탐색 (BFS)

---

🧐 문제 설명

---

😍 나의 풀이

BFS로 풀이하면 되는데 무한 루프에 빠지는 실수를 했다.

나는 연결 관계를 표현하는 graph 리스트와 각 지점에 도달하는 경로의 길이를 저장하는 route 리스트를 만들어 graph에서 상,하,좌,우 이동하여 인접한 지점이 1이면 그 인덱스 좌표를 큐에 집어 넣고 graph와 같은 크기의 route에는 길이를 +1 했다.

그런데 이렇게 풀이하니까 되돌아가는 경우에 대해서도 route 값이 계속 커져서 무한루프에 빠지는 문제점이 있었다. 그래서 route를 사용하지 않고 graph에 바로 길이를 초기화했다.

→ graph에 값이 1일 때만 이동하는데, 이미 지나간 지점은 1보다 큰 길이의 값이기 때문에 되돌아가는 경로가 존재할 수 없어서 모든 탐색이 가능하다.

if 0<=nx<M and 0<=ny<N:
              if graph[ny][nx] == 1:
                  queue.append([ny, nx])
                  graph[ny][nx] = graph[y][x] + 1

만약, 원래 생각했던 대로 경로의 길이를 저장하는 리스트를 따로 만들었다면 visited 리스트를 만들어서 이미 방문 처리된 지점에 대해서는 다시 탐색하지 않는 방식으로 풀이해야한다.

from collections import deque
N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

def bfs(start_x, start_y):
    dx = [-1, 1, 0, 0]   # 좌우
    dy = [0, 0, -1, 1]   # 상하

    queue = deque([[start_x, start_y]])

    while queue:
        y, x = queue.popleft()

        if y == N and x == M:
            break

        for i in range(4):
            nx = x + dx[i]  # 좌우
            ny = y + dy[i]  # 상하

            if 0<=nx<M and 0<=ny<N:
                if graph[ny][nx] == 1:
                    queue.append([ny, nx])
                    graph[ny][nx] = graph[y][x] + 1

    return graph[N-1][M-1]

print(bfs(0, 0))