백준 14940 쉬운 최단거리

📃 문제

💟 코드

# 백준 14940 쉬운 최단거리
from collections import deque

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
visited = [[-1]*m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if lst[i][j] == 2:
            Q = deque([[i, j]])
            visited[i][j] = 0
            while Q:
                r, c = Q.popleft()
                dr = [-1, 1, 0, 0]
                dc = [0, 0, -1, 1]
                for k in range(4):
                    nr = r + dr[k]
                    nc = c + dc[k]
                    if 0 <= nr < n and 0 <= nc < m:
                        if visited[nr][nc] == -1:
                            if lst[nr][nc] == 1:
                                visited[nr][nc] = visited[r][c] + 1
                                Q.append([nr, nc])
                            else:
                                visited[nr][nc] = 0
        elif lst[i][j] == 0:
            visited[i][j] = 0
for i in range(n):
    print(*visited[i])

✨ 코드 풀이

1. visited라는 지도와 같은 크기의 2차원배열을 만들고 모두 -1로 채워준다.
2. 2차원 배열 안의 값이 2일 때만 Q라는 덱에 해당 위치를 쌓고 visited값을 0으로 변경한다.
3. Q에 값이 존재하지 않을 때 까지 Q의 제일 앞에 있는 값을 뽑아 상하좌우로 이동시킨다.
4. 이동시킨 값이 지도를 벗어나지 않고, 이동시킨 값의 visited값이 -1이고, 이동시킨 값의 지도 값이 1인 경우에만 이동시킨 값의 visited값을 이전의 visited값에 1을 더한 값으로 지정한다.
5. 이동한 위치를 Q에 쌓아준다.
6. 이동했을 때 지도의 값이 1이 아니면 visited값은 0.
7. 제일 처음 반복문에서 값이 2가 아닌 0일 때는 visited값을 0으로 지정시킨다.
   => 이걸 해주는 이유는 2의 위치에서 사방이 막혀있을 때 지도에서 값이 0인곳의 visited값을 바꿔줄 수 없기 때문에!!!