BOJ - 14940

백준 문제 링크
쉬운 최단거리

❓접근법

1. BFS를 사용했다.
2. 방문 처리할 변수 visited와 거리를 저장할 변수 cnt를 만들었다.
3. 먼저 목표지점 2의 좌표를 구해 start_x, start_y에 저장해준다.
4. bfs 함수에서
   새로운 좌표(nx,ny)에 방문하지 않았고, 지도에서 갈 수 있는 땅이면
   방문처리하고, cnt[nx][ny] = cnt[x][y] + 1로 거리를 저장 후 queue에 넣어주었다.
5. 마지막으로 목표 지점부터 시작할 것이므로 목표 지점 좌표 값은 0으로,
   문제에서 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1 이라고 했으므로 이중 반복문으로 지도에서 1인 부분 중 visited에서 방문 처리되지 않은 좌표의 값은 -1로 만들었다.

👌🏻코드

from collections import deque

n, m = map(int, input().split())

graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

start_x, start_y = 0,0

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            start_x, start_y = i,j
            
cnt = [[0] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]

def bfs(x,y):
    
    queue = deque()
    queue.append((x,y))
    
    visited[x][y] = True
    
    
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    while queue:
        x,y = queue.popleft()
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            
            if (0<=nx<n) and (0<=ny<m) and not visited[nx][ny]:
                if graph[nx][ny] == 1:
                    visited[nx][ny] = True
                    cnt[nx][ny] = cnt[x][y] + 1
                    queue.append((nx,ny))
                    

        
bfs(start_x, start_y)
cnt[start_x][start_y] = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] != 0 and not visited[i][j]:
            cnt[i][j] = -1

for i in range(len(cnt)):
    print(* cnt[i])