백준 14940: 쉬운 최단거리 - BFS(파이썬)

쉬운 최단거리 성공

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

def bfs(x_start,y_start):
    queue=deque()
    queue.append([x_start,y_start])

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

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            #다음 좌표가 범위 밖이면 불가능. continue.
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            #다음 좌표가 이미 방문한 좌표면 할 필요 X. continue.
            if answer[nx][ny]!=-1:
                continue

            #아직 방문하지 않은 유효한 좌표면, 이전 좌표의 answer값에 1을 더한 것으로 값을 세팅하고 덱에 저장.
            answer[nx][ny]=answer[x][y]+1
            queue.append([nx,ny])


#메인 코드 부분
n,m=map(int, sys.stdin.readline().split()) #세로 n, 가로 m

#북동남서(변화율)
dx=[-1,0,1,0]
dy=[0,1,0,-1]

#지도 입력받기
myMap=[]
for i in range(n):
    myMap.append(list(map(int,sys.stdin.readline().split())))


#정답 배열 세팅하기
answer=[]
x_start,y_start=0,0 #여기에 출발점을 저장할 것임.
for i in range(n):
    answer.append([])
    for j in range(m):
        if myMap[i][j]==2: #출발점이면 이 좌표를 기억하고 0으로 표시.
            x_start, y_start=i, j #출발점 좌표!
            answer[i].append(0)
        elif myMap[i][j]==1: #갈 수 있는 땅이면 -1로 표시.
            answer[i].append(-1)
        else: #갈 수 없는 땅이면 0으로 표시.
            answer[i].append(0)

#출발점에서 BFS 시작.
bfs(x_start,y_start)

#정답 배열 출력
for i in range(n):
    for j in range(m):
        print(answer[i][j], end=' ')
    print()

 

풀이 및 접근)

- 문제를 보자마자 이전에 푼 최단거리 미로 문제가 떠올랐다. 특정 점에서 모든 점들까지 도달하는 최단 거리를 구하는 것이다. 이러한 유형은 BFS를 통해 구하면 된다. DFS는 일단 끝까지 계속 가기 때문에 최단거리를 구하는 데에 적합하지 않고, BFS를 통해 주변의 것들을 우선적으로 훓으면서 주변의 값들을 업데이트 시키면 된다.

- 우선 주어진 지도와 크기가 같은 배열을 생성한 후, 출발점 값과 갈 수 없는 땅을 0으로 하고, 갈 수 있는 땅을 -1로 한다.

- 이 문제에서 visited[][] 배열 등을 도입하여 방문 여부를 따질 수도 있지만, 그럴 필요가 없다. 갈 수 있는 땅을 -1로 했으므로, 방문한 적이 있으면 -1이 아닌 다른 값으로 대체되어 있을 것이기 때문이다. 따라서 방문 여부를 따질 때는 그 값이 -1인지만 체크하면 해결된다.

- 이 외의 코드들은 여느 BFS의 문제와 다를 것 없다.