[Python] 백준 2178번 미로찾기(DFS/BFS)

문제 풀이 (BFS)

• 방문여부를 확인 할 별도의 리스트를 만들지 않고 그래프 내에서 연산 수행
• 상하좌우를 탐색하며, 이동할 때 마다 그래프의 값을 이전 값 + 1로 업데이트
• 도착 위치의 값 출력 (최단 거리)

코드

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

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

def bfs(y, x):
    queue = deque()
    queue.append((y, x))

    while queue:
        y, x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            # 이동할 좌표의 값이 이동가능한 곳이라면 이전에 이동하기 전 좌표값에
            # (이전 까지 이동한 거리의 수가 이전 좌표에 담겨있음) 1을 더해서 넣어주고,
            # 큐에 다시 이동할 좌표 값을 넣어 탐색진행
            if 0 <= ny < r and 0 <= nx < c and graph[ny][nx] == 1:
                graph[ny][nx] = graph[y][x] + 1
                queue.append((ny, nx))

    return graph[r - 1][c - 1]

print(bfs(0, 0))