[BOJ #14940] 쉬운 최단거리

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

 

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

 

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

 

내가 쓴 코드

from sys import stdin; input = stdin.readline
from collections import deque
di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]

def bfs(a, b):
    q = deque()
    q.append([a, b])
    ans[a][b] = 0

    while q:
        ci, cj = q.popleft()
        for k in range(4):
            ni = ci + di[k]
            nj = cj + dj[k]
            if 0<=ni<n and 0<=nj<m and arr[ni][nj] and ans[ni][nj] == -1:
                    ans[ni][nj] = ans[ci][cj] + 1
                    q.append([ni, nj])

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

# 2 인 곳을 찾아 x, y 에 저장
x, y = 0, 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 2:
            x = i
            y = j
            # 2 였던 곳을 0 으로 대체
            arr[i][j] = 0
            break
# 2 인 곳에서 bfs 시작
bfs(x, y)

# arr 가 0인 곳은 ans 도 0 으로 입력
for i in range(n):
    for j in range(m):
        if not arr[i][j]:
            ans[i][j] = 0

for a in ans:
    print(*a)

bfs 정복학기 첫단계.. 첫 문제... ㅋㅋㅋ.. 진짜 bfs의 개념을 다질 수 있는 문제였던 것 같다. bfs 기억 안나면 또 이 문제 풀어보기 !!

 

제출 결과