(Python/🥈1)백준리즘알고즘 14940번 :쉬운 최단거리

 

문제 바로가기 

쉬운 최단거리

문제:

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라. 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력:

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력:

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

 

풀이 :

import sys
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m = map(int, sys.stdin.readline().rstrip().split(" "))
Q = deque()

graph = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            Q.append([i, j])
            graph[i][j] = 0

while Q:
    x, y = Q.popleft()
    visited[x][y] = True
    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1 and not visited[nx][ny]:
            graph[nx][ny] = graph[x][y] + 1
            Q.append([nx, ny])
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and not visited[i][j]:
            graph[i][j] = -1

for i in graph:
    print(*i)

 

전형적인 bfs 문제