[백준 파이썬 2178] 미로 탐색 (실버 1)

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

2178번: 미로 탐색

from collections import deque

N, M = map(int, input().split()) # N 행 M 열 입력 받기
adj = [list(map(int, input())) for _ in range(N)] # 미로 행렬 저장
visited = [[False] * M for _ in range(N)] # 미로 방문 행렬 저장
q = deque() # bfs용 큐
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(y, x):
    q.append((y, x))
    visited[y][x] = True
    while q:
        oy, ox = q.popleft()
        for i in range(4):
            ny = oy + dy[i]
            nx = ox + dx[i]
            if (0 <= ny < N and 0 <= nx < M) and adj[ny][nx] !=0 and not visited[ny][nx]:
                q.append((ny, nx))
                visited[ny][nx] = True
                adj[ny][nx] = adj[oy][ox] + 1 # 미로 행렬의 값이 곧 최단 거리
bfs(0, 0)

print(adj[N-1][M-1]) # 무조건 길은 있다고 했으니 N행 M열 값을 출력

그냥 간단한 최단거리 찾는 문제. 최단거리니까 bfs 로 풀었다. 

시작 좌표 (0, 0), 끝좌표 (N-1, M-1) 로 정해져 있어서 그냥 bfs 돌리고 마지막에 N행 M열 값을 출력했다. 

 

bfs는 0, 0을 시작으로 해서 방문한 곳은 visited 값을 True로, 그리고 상하좌우 중 범위 안 넘고 0 아닌 곳(못가는 곳), 방문 안 한 곳이면 큐에 넣어서 adj 값을 현재보다 +1 하게 하여 최단거리를 저장하게 했다. 

 

시작 최단거리는 1인데 (0, 0) 값도 1부터 시작해서 추가적인 처리 없이 바로 돌릴 수 있었다. 

 

---

4 6
101111
101010
101011
111011

 

예제 입력 1을 넣으면

[1, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]

 

bfs 돌린 adj 는 이렇게 되고, 그래서 최단거리는 15가 된다.