[BOJ#14940] 쉬운 최단거리

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

14940번: 쉬운 최단거리

1 초

128 MB

24574

9715

7918

37.132%

문제

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

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

입력

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

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

출력

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

---

제출 코드

import sys
from collections import deque
input = sys.stdin.readline

di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]

def bfs(si, sj):
    visited[si][sj] = True
    q = deque()
    q.append([si, sj])
    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 not visited[ni][nj] and arr[ni][nj] != 0:
                visited[ni][nj] = True
                cnt[ni][nj] = cnt[ci][cj] + 1
                q.append([ni, nj])
        

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
cnt = [[0] * M for _ in range(N)]

for i in range(N):
    for j in range(M):
        if arr[i][j] == 2:
            bfs(i, j) # 갈 수 있는 땅 체크
            
for i in range(N):
    for j in range(M):
        if not visited[i][j] and arr[i][j] == 1:
            cnt[i][j] = -1
for line in cnt:
    print(*line)

그래프 실버 1까지는 무난하게 풀게된 것 같다. 기계적으로 코드를 적어서 공부가 됐는지 모르겠다..

다 풀어놓고 언팩을 안해서 틀려버린