[백준] 14940번 - 쉬운 최단거리

📩 출처

문제

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

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

입력

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

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

출력

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

👉 생각

• 이차원 배열에서 먼저 2의 좌표값을 찾는다.
• 시작점부터 상하좌우 값이 1이고 방문하지 않은 곳은 너비우선 탐색을 하면서 방문 체크 배열 visited의 값을 증가시켜 나간다.
• 탐색이 끝나면 아직 방문하지 않았고 arr의 값이 1인 좌표의 값을 -1로 바꿔서 출력한다.

from collections import deque
import sys

def bfs(x, y):
    q = deque([(x, y)])
    while q:
        x, y = q.popleft()

        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == 1 and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = visited[x][y] + 1

n, m = map(int, input().split())
arr = [list(map(int, list(sys.stdin.readline().split()))) for _ in range(n)]
visited = [[0] * m for _ in range(n)]

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

for i in range(n):
    for j in range(m):
        if not visited[i][j] and arr[i][j] == 1:
            visited[i][j] = -1

for i in visited:
    print(*i)