BOJ 14940번: 쉬운 최단거리

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

14940번: 쉬운 최단거리

 

n*m의 배열의 각각의 지점에서 목표지점까지의 최단거리를 출력하는 문제이다.

거꾸로 생각하면 목표지점에서 각각의 지점까지의 최단거리를 출력하는 문제가 되기 때문에, 목표지점을 시작 인덱스로 놓고 BFS탐색을 이용하여 풀 수 있다.

queue를 이용한 반복문 반식으로 BFS를 구현하였고, 처음에는 도달하지 못하는 곳은 모두 -1로 출력을 하도록 만들어서 틀렸는데, 0인데 도달하지 못하는 경우에는 0을 출력해야 했다. 따라서 주어진 배열을 돌면서 0인 경우에는 정답 배열에 0을 넣어주는 코드를 추가하였다.

 

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
arr = []
ans = [[-1]*m for _ in range(n)]
visit = [[False]*m for _ in range(n)]

for _ in range(n):
    arr.append(list(map(int, input().split())))
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()

def solve(x, y): #2의 위치
    q.append([x, y, 0])
    ans[x][y] = 0
    visit[x][y] = True
    while (q):
        v = q.popleft()
        for i in range(4):
            xx = v[0] + dx[i]
            yy = v[1] + dy[i]
            if (xx>=0 and xx<n and yy>=0 and yy<m and visit[xx][yy]==False):
                visit[xx][yy] = True
                if(arr[xx][yy]>0):
                    ans[xx][yy] = v[2]+1
                    q.append([xx,yy,v[2]+1])
for i in range(n):
    for j in range(m):
        if (arr[i][j] == 0):
            ans[i][j] = 0
            
        elif (arr[i][j]==2):
            solve(i,j)
            
for i in range(n):
    print(' '.join(map(str, ans[i])))