[백준] 14940번 쉬운 최단거리 파이썬 풀이

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

14940번: 쉬운 최단거리

 

---

1. 접근 방식

• (x, y) 지점의 상하좌우 지점으로부터 최단 거리를 알아낼 수 있다.

 오직 가로와 세로로만 움직일 수 있으므로, 어떤 지점에서 이동할 수 있는 경로는 상하좌우밖에 없다.

 

 예를 들어 2의 위치가 (1, 1)일 때, 이 지점의 상하좌우 즉 (0, 1), (2, 1), (1, 0), (1, 2) 지점으로부터 2까지 가는 최단 거리는 1이다. (1, 1) 지점의 값이 0이고, 그곳으로 이동하는 데 +1이 된 것이다.

이와 마찬가지로, (0, 0)은 (1, 0) 혹은 (0, 1) 지점으로부터 한 칸 이동하면 갈 수 있다. (1, 0)이든 (0, 1)이든 해당 지점의 값이 1이고, 여기에 1을 더하여 (0, 0)에서 2까지 이동하는 최단 거리는 2가 된다.

 

 이 방법을 적용하려면 먼저 2가 어느 위치에 있는지 파악해야 한다.

 

 

• 방문 여부를 파악하는 방법

 정답 행렬의 원소 값을 모두 -1로 초기화한 후, 원래 갈 수 없는 땅의 위치를 0으로 변경한다.

 이후 bfs 방식으로 지도를 탐색할 텐데, 그러면  자연스럽게 방문할 수는 있지만 도달할 수 없는 위치는 -1로 남아 있게 된다.

 

 

• 시간을 줄이자.

 n과 m의 각각 최대 1,000이 될 수 있다. 즉, 지도의 크기가 1,000,000이 될 수 있단 의미이다. 따라서 처음에 지도 정보를 입력 받는 시간을 줄이기 위해 일반 input()이 아닌, sys.stdin.readline()을 활용한다.

 

 또한 정답 결과를 출력하는 print에서도 시간을 줄여야 한다.

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

위 코드처럼 2중 반복문으로 원소를 하나씩 출력하는 것보단, 아래 정답 코드에서처럼 한 행씩 join하여 출력하는 편이 더 빠르다.

 

 

 

2. 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

def setting():
    row, col = len(maps), len(maps[0])
    array = [[-1] * col for _ in range(row)]
    for i in range(row):
        for j in range(col):
            if maps[i][j] == 2:
                array[i][j] = 0
                target = (i, j)

            elif maps[i][j] == 0:
                array[i][j] = 0
    return target, array

def solve(i, j):
    waiting = deque([(i, j)])

    while waiting:
        r, c = waiting.popleft()

        for d in directions:
            x, y = r + d[0], c + d[1]

            if x < 0 or x >= n or y <0 or y >= m:
                continue

            if result[x][y] > -1:
                continue

            result[x][y] = result[r][c] + 1
            waiting.append((x, y))


n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

pos, result = setting()
solve(pos[0], pos[1])

for r in result:
    print(' '.join(list(map(str, r))))