Baekjoon [14940] 쉬운 최단거리 - python

문제

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

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

입력

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

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

출력

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

예제 입력

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

문제 풀이

from collections import deque

n,m = map(int,input().split())
visitied = [[0 for _ in range(m)] for _ in range(n)]
new_map = [[0 for _ in range(m)] for _ in range(n)]
matrix = []
for i in range(n):
    matrix.append(list(map(int,input().split())))

def bfs(i,j,cnt):
    que = deque()
    que.append((j,i,cnt)) # x,y
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    while que:
        x,y,num = que.popleft()
        if visitied[y][x] == 1:
            continue
        visitied[y][x] = 1
        new_map[y][x] = num
        # print(num)
        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if 0 <= next_x < m and 0 <= next_y < n:
                if visitied[next_y][next_x] == 0 and matrix[next_y][next_x] == 1:
                    que.append((next_x,next_y,num+1))

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 2:
            bfs(i,j,0)

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1 and new_map[i][j] == 0:
            new_map[i][j] = -1

for i in range(n):
    for j in range(m):
        print(new_map[i][j], end = " ")
    print()

문제 해석

BFS를 이용해 탐색을 진행합니다. 거리를 계산하기보단 도착지에서 출발하여 거리가 얼마나 먼지 계산했습니다. 이후 -1, 갈 수 있는 땅이지만 0에 막혀 가지 못할 경우 new_map에 0이 찍히기 떄문에 탐색을 통해 0이 있으면 -1로 바꿔줍니다.