문제 설명

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

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

입력

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

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

출력

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

풀이 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import sys

n, m = map(int, sys.stdin.readline().split())


regions = []

dest = [-1, -1]
for i in range(n):
    region_row = list(map(int, sys.stdin.readline().split()))
    if 2 in region_row:
        dest = [i, region_row.index(2)]
    regions.append(region_row)

dists = [[-1 if regions[i][j] else 0 for j in range(m)] for i in range(n)]


dest.append(0)
points = [dest]
visited = {}

for i in range(n):
    for j in range(m):
        visited[(i, j)] = False

d_x = [1, -1, 0, 0]
d_y = [0, 0, 1, -1]

while points:
    p_y, p_x, dist = points.pop(0)
    dists[p_y][p_x] = dist
    if visited[(p_y, p_x)]:
        continue
    else:
        visited[(p_y, p_x)] = True
    # print(p_y, p_x, dist)
    if dist == 0 and (p_y, p_x) != (dest[0], dest[1]):
        continue

    for i in range(4):
        new_x, new_y = p_x + d_x[i], p_y + d_y[i]
        if (new_x >= 0 and new_x < m) and (new_y >= 0 and new_y < n):
            if visited[(new_y, new_x)]:
                continue

            if regions[new_y][new_x] == 0:
                points.append([new_y, new_x, 0])
            else:
                points.append([new_y, new_x, dist + 1])


for d in dists:
    print(" ".join(map(str, d)))

CHECK!

n, m 이 각각 y, x 임을 헷갈려서 틀리는 경우가 많음
내 경우는 출력 형식을 제대로 맞추지 않아서 틀렸음
- 리스트 그대로가 아니라 리스트의 원소들을 한 줄에 출력했어야 했음
그 외에도 갈 수 있지만 벽에 막혀 도달하지 못하는 곳을 -1로 출력하는 등의 추가적인 예외처리가 필요함
코드를 좀 더 깔끔하게 하면 좋을 것 같고, 복습 겸 한번 더 풀어봐야 할 듯