[Python/Silver1/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
input = sys.stdin.readline

class Solution:
    def short_dist(self):
        n,m = map(int, input().split())
        grid = []
        for _ in range(n):
            grid.append(list(map(int, input().split())))

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    start = [i,j]
                    break

        def is_valid(i,j):
            return 0 <= i < n and 0 <= j < m
            
        visited = [[False]*m for _ in range(n)]
        def bfs(i,j):
            Q = deque()
            Q.append((i,j,0))
            grid[i][j]=0
            visited[i][j] = True
            while Q:
                x, y, k= Q.popleft()
                for dx, dy in ((-1,0),(1,0),(0,-1),(0,1)):
                    nx, ny = x + dx, y + dy
                    if is_valid(nx, ny) and not visited[nx][ny] and grid[nx][ny] == 1:
                        visited[nx][ny] = True
                        grid[nx][ny] = k+1
                        Q.append((nx,ny,k+1))
        
        bfs(start[0], start[1])
        
        for i in range(n):
            for j in range(m):
                if not visited[i][j] and grid[i][j] == 1:
                    grid[i][j] = -1
                    
        for g in grid:
            print(*g)



if __name__ == "__main__":
    s = Solution()
    s.short_dist()

 

 

 

|    비고

전형적인 bfs 문제, visited를 잘 사용하는 게 이 문제의 핵심이다.