백준 #14940 - [S1] 쉬운 최단거리 : BFS, Queue

(python3)

14940번: 쉬운 최단거리

 

 

큐를 활용한 BFS 로 최단거리 구하기

시작점에서부터 다른 점들까지의 최단 거리를 구하는 문제이기 때문에 너비 우선 탐색으로 진행하면 해결할 수 있습니다. BFS 는 큐를 활용해서 구현하는게 가장 대표적입니다.

기본 아이디어는, 탐색을 진행할때마다 새로운 탐색 지점들을 큐에 넣고, 큐에서 지점을 하나씩 빼서 그 지점의 다음 단계 탐색을 진행하는걸 반복하는 겁니다. 그러면 깊이가 깊은 노드들이 큐의 뒷쪽으로 쌓이면서 bfs 를 수행할 수 있게 됩니다.

 

파이썬 collections 의 deque 에 구현되어있는 덱 자료구조를 사용했습니다. 덱 자료구조는 FI, LI, FO, LO 을 자유롭게 구사할 수 있어서 큐와 스택을 모두 수행할 수 있는 자료구조 입니다.

 

코드

import sys
from collections import deque
def solution(input) :
    # bfs, 위치 저장
    # 입력받기
    R,C = list(map(int,input().split()))
    MAP = []
    for _ in range(R) :
        MAP.append(list(map(int,input().split())))
    dist_map = [[-1 for _ in range(C)] for _ in range(R)]
    D = [(-1,0),(1,0),(0,-1),(0,1)]

    def inicialize_and_find_2() :
        r2,c2 = 0,0
        for r in range(R) :
            for c in range(C) :
                if MAP[r][c] == 2 :
                    r2,c2 = r,c
                elif MAP[r][c] == 0 :
                    dist_map[r][c] = 0
        return r2,c2

    def bfs(r,c) :
        deq = deque([(r,c,0)])
        dist_map[r][c] = 0

        while deq :
            r,c,lev = deq.popleft()
            for dr, dc in D :
                nr = r+dr
                nc = c+dc
                if nr >= 0 and nr < R and nc >= 0 and nc < C :
                    if MAP[nr][nc] == 1 and dist_map[nr][nc] == -1 :
                        dist_map[nr][nc] = lev+1
                        deq.append((nr,nc,lev+1))
    
    r,c = inicialize_and_find_2()
    bfs(r,c)

    for r in range(R) :
        print(' '.join(str(i) for i in dist_map[r]))
        
input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac