백준 14940번 쉬운 최단거리

그냥 bfs로 최단거리를 구하면 된다.

 

from collections import deque
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
graph=[]
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip().split())))

q=deque()
visited=[[-1]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if graph[i][j]==2:
            q.append([i,j])
            visited[i][j]=0
dr=[-1,0,1,0]
dc=[0,1,0,-1]
while q:
    cur_row,cur_col=q.popleft()
    for i in range(4):
        row=cur_row+dr[i]
        col=cur_col+dc[i]
        if row>=n or row<0 or col>=m or col<0:
            continue
        if graph[row][col]==0:
            visited[row][col]=0
            continue
        if visited[row][col]!=-1:
            continue
        visited[row][col]=visited[cur_row][cur_col]+1
        q.append([row,col])
for i in visited:
    print(*i)

이렇게 작성했는데

틀렸다.

 

문제를 덜읽었었다.

마지막에 도달할수없으면서 1인 부분은 -1로 출력하라는걸 못봤다.

조금 더 수정해주자

도달하지 못한 0이 -1로 나올테니까 수정한다.

 

from collections import deque
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
graph=[]
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip().split())))

q=deque()
visited=[[-1]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if graph[i][j]==2:
            q.append([i,j])
            visited[i][j]=0
        elif graph[i][j]==0:
            visited[i][j]=0
dr=[-1,0,1,0]
dc=[0,1,0,-1]
while q:
    cur_row,cur_col=q.popleft()
    for i in range(4):
        row=cur_row+dr[i]
        col=cur_col+dc[i]
        if row>=n or row<0 or col>=m or col<0:
            continue
        if visited[row][col]!=-1:
            continue
        visited[row][col]=visited[cur_row][cur_col]+1
        q.append([row,col])
for i in visited:
    print(*i)

이렇게 수정해줬다.