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

문제

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

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

입력

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

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

출력

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

풀이
문제를 보자마자 bfs를 떠올렸다 목표 지점에서 탐색을 시작하면 되는데, 목표 지점의 위치가 어디인지 알 수 없기 때문에 완전 탐색으로 위치를 찾아서 bfs를 수행한다
n과 m의 범위가 1000까지 이기 때문에 이렇게 해도 문제가 없고, visited를 따로 선언하지 않아도 방문 여부와 거리를 기록할 수 있을 것 같은데 나의 경우에는 -1과 0을 구분해주는 것에서 같은 리스트를 사용하는게 더 헷갈릴 것 같아 우선은 따로 선언해서 사용했다
bfs를 다 돌고나면 목표 지점으로부터의 거리가 모두 기록되어있을 것인데 중요한 점은 원래 갈 수 없는 땅인 경우에는 0을 출력해야한다
따라서 완전 탐색으로 다시 한번 값을 바꿔주는 과정을 추가했다

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

grid = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dist = [[-1]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]

def bfs(i,j):
    dxs = [0,0,1,-1]
    dys = [1,-1,0,0]
    q = deque([(i,j)])
    visited[i][j] = True

    while q:
        x, y = q.popleft()

        for dx, dy in zip(dxs, dys):
            nx, ny = dx+x, dy+y
            if 0<=nx<=n-1 and 0<=ny<=m-1:
                if grid[nx][ny] == 0:
                    dist[nx][ny] = 0
                elif not visited[nx][ny] and grid[nx][ny] == 1:
                    q.append((nx, ny))
                    dist[nx][ny] = dist[x][y] + 1
                    visited[nx][ny] = True

flag = False
for i in range(n):
    for j in range(m):
        if grid[i][j] == 2:
            dist[i][j] = 0
            bfs(i,j)
for i in range(n):
    for j in range(m):
        if grid[i][j] == 0:
            dist[i][j] = 0
            
for elem in dist:
    print(*elem)