[백준 14940 🥈] 쉬운 최단거리

https://www.acmicpc.net/problem/14940

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

n,m=map(int, sys.stdin.readline().split(' '))
area=[list(map(int, sys.stdin.readline().split(' '))) for _ in range(n)]

visited = [[0] * (m) for _ in range(n)]
dist=[[0]*(m) for _ in range(n)]
def bfs(starty, startx):
    global visited, area, dist
    queue=deque()
    queue.append((starty, startx,0))
    visited[starty][startx]=1
    directions=[(0,1),(1,0),(0,-1),(-1,0)]
    while queue:
        y,x,d=queue.popleft()
        for di in directions:
            dy=y+di[0]
            dx=x+di[1]
            if 0<=dy<n and 0<=dx<m and visited[dy][dx]==0 and area[dy][dx]==1:
                queue.append((dy,dx,d+1))
                dist[dy][dx]=d+1
                visited[dy][dx]=1


# 시작 지점 찾기
for i in range(n):
    for j in range(m):
        if area[i][j]==2:
            bfs(i,j)
            # 출력하고,프로그램 종료
            for y in range(n):
                for x in range(m):
                    # 기존에 갈 수 있는 경로지만, 목적지에 도달할 수 없는 지역인 경우
                    if dist[y][x]==0 and area[y][x]==1:
                        dist[y][x]=-1
            for y in range(n):
                print(*dist[y], sep=' ')
            sys.exit(0)

• BFS를 이용하면 간단한 문제다!
• 입력받은 지점의 정보 배열 area를 돌면서, area 값이 2인 목표지점을 찾아서 그 위치부터 bfs를 돌면서 상하좌우로 목표지점으로부터 몇 번째로 방문하는 위치인지 변수 d에 저장해주고 각 지점의 거리를 저장한 dist 배열을 갱신해주면 된다. 
• 그리고 기존에 갈 수 있는 경로지만(area 값이 1), 목적지에 도달할 수 없는 지역이라 dist 값이 0인 위치는 -1로 갱신해준다.