백준 14940 쉬운 최단거리 Python

🐸 문제 정보

14940번: 쉬운 최단거리

 

🤖 알고리즘

BFS

 

⏱️ 풀이 시간

10.06m

 

📝 풀이

BFS의 정석 같은 문제였다.

딱히 구현이 추가되거나 복잡하게 꼬여있는 것 없이, BFS 이론만 적용해서 풀 수 있는 문제였다.

 

도달하지 못하는 곳에는 -1을 넣어줘야하는게 복잡해 보일 수 있지만, 오히려 -1로 새로운 지도 배열을 선언해놓고 BFS 돌면서 값을 채워준다면 도달하지 못하는 곳에 자연스럽게 -1이 남게된다.

 

🧑‍💻 나의 답

# pypy3

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

n, m = list(map(int, input().rstrip().split()))
board = [list(map(int, input().rstrip().split())) for _ in range(n)]
new_map = [[-1] * m for _ in range(n)]
start = (0, 0)

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    for j in range(m):
        if board[i][j] == 2:
            start = (i, j)
            new_map[i][j] = 0
        elif board[i][j] == 0:
            new_map[i][j] = 0

q = deque([start])
while q:
    px, py = q.popleft()
    for i in range(4):
        nx, ny = px + dx[i], py + dy[i]
        if (0 <= nx < n) and (0 <= ny < m) and (new_map[nx][ny] == -1):
            new_map[nx][ny] = new_map[px][py] + 1
            q.append((nx, ny))

for line in new_map:
    print(*line, sep=' ')