boj.kr/2178 미로 탐색 (silver1) 파이썬 풀이

1. 아래와 같이 bfs방식으로 거리값을 증감하면서 좌표를 탐색하고 목적지에 도착한 경우 최단거리값을 출력

1.1. 출발지 좌표와 초기 거리값을 deque에 추가

1.2. dq가 빌 때까지 아래를 반복

1.2.1. dq.popleft하여 현재좌표와 거리값을 저장

1.2.2. 현재 좌표가 목적지 좌표이면 거리값을 반환

1.2.3. 상하좌우 좌표를 검사하면서 좌표값이 '1'이고 방문하지 않은 경우 방문체크하고 deque에 좌표, 현재거리+1을 append

2. bfs함수 호출 결과를 출력

 

N, M = map(int, input().split())
board = [input().strip() for _ in range(N)]
visited = [[0] * M for _ in range(N)]

dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)
from collections import deque
def bfs():
    dq = deque()
    dq.append((0, 0, 1))
    while dq:
        (cy, cx, d) = dq.popleft()
        if cy == N - 1 and cx == M - 1:
            return d
        for i in range(4):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0 <= ny < N and 0 <= nx < M and board[ny][nx] == '1' and visited[ny][nx] == 0:
                visited[ny][nx] += 1
                dq.append((ny, nx, d + 1))

print(bfs())

 

bfs는 최단거리를 찾는 문제에서 사용할 수 있다.