[백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS)

알고리즘 유형 : 다익스트라 or BFS
풀이 참고 없이 스스로 풀었나요? : △

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

SOLVE 1

다익스트라 풀이

import sys
import heapq
input = sys.stdin.readline
INF = float('inf')

N, K = map(int, input().split())

# 인접 노드들을 iterable한 값으로 리턴하기 위한 제너레이터 함수
# 코드가 간단해짐
def move(x):
    yield (x-1, 1)
    yield (x+1, 1)
    yield (2*x, 0)

# 다익스트라 알고리즘
def N_to_K(N, K):
    SSSP = [INF]*(100001)
    SSSP[N] = 0
    q = [(0, N)]
    
    while q:
        cnt_time, cnt_x = heapq.heappop(q)
        
        if cnt_time > SSSP[cnt_x]:
            continue
        
        # 0부터 100000까지의 모든 노드들은, 조건 범위 안에서
        # 자신의 -1, +1, *2의 인접 노드를 가짐
        # 그래서 제너레이터를 통해 직접 인접 노드를 구하여 순회하면 됨
        for adc_x, adc_time in move(cnt_x):
            cal_time = cnt_time + adc_time
            
            # 인접 노드로 구한 값이 조건 범위 안에 있어야 함
            if 0 <= adc_x <= 100000 and cal_time < SSSP[adc_x]:
                SSSP[adc_x] = cal_time
                heapq.heappush(q, (cal_time, adc_x))
    
    return SSSP[K]

print(N_to_K(N, K))

SOLVE 2

BFS 풀이

import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().split())

# BFS는 한 번 방문한 노드는 다시 방문하지 않음
# 따라서 같은 level에 대하여 인접 노드로의
# 가중치가 0인 2*x부터 방문해야 함
def move(x):
    yield (2*x, 0)
    yield (x-1, 1)
    yield (x+1, 1)

def BFS(start):
    elapsed = [-1]*(100001)
    elapsed[start] = 0
    q = deque([start])
    
    while q:
        cnt_x = q.popleft()
        
        if cnt_x == K:
            return elapsed[K]
        
        for nx, adc_time in move(cnt_x):
            cal_time = elapsed[cnt_x] + adc_time
            if 0 <= nx <= 100000 and elapsed[nx] == -1:
                elapsed[nx] = cal_time
                q.append(nx)

print(BFS(N))

SOLVE 1) 풀이 요약 (다익스트라 풀이)

1. 이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다.

   0부터 10만까지의 노드가 있고, 모든 노드는 0이상 10만 이하의 범위 안에서 -1, +1, x2의 노드와 간선으로 연결이 되어 있는 그래프이고 간선의 가중치는 0 또는 1이다.

   가중치가 모두 0 또는 양수이고, 특정 노드에서 특정 노드까지의 최단 경로 가중치를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다.

2. 기존의 다익스트라 형태에서 조금 다른 점은, 그래프 간선 정보가 따로 주어지는게 아니라, 현재 노드에 대해 -1, +1, x2를 인접 노드로 정의하고 순회하면 된다. 이를 위해 제너레이터를 사용한다.

3. 이 때 인접 노드 중 범위를 벗어나는 경우를 조건문으로 걸러줘야한다.

   마지막에 K 노드의 최단 경로 가중치 값을 리턴하면 끝이다.

SOLVE 2 풀이 요약 (BFS 풀이)

1. BFS를 약간 변형한 풀이이다.

2. BFS는 인접 노드들을 너비 우선 탐색하면서 최단 경로를 찾는 알고리즘이다.

   다만 이 문제는 0과 1의 가중치가 있는 그래프가 대상이기 때문에, BFS를 사용하려면 약간의 변형을 생각해봐야한다.

   우선 BFS는 가중치가 없는 그래프에서 가장 먼저 목표 노드를 찾았을 때, 그 때까지의 경로가 최단 경로임이 보장된다.

   이 문제에서 너비 우선 탐색했을 때 최단 경로임을 보장하려면, 그래프의 어떤 노드의 인접 노드를 탐색할 때 가중치가 0인 노드부터 먼저 방문해야한다.

   서로 같은 level에 위치한 노드들 중에서, 가중치가 0인 노드는 가중치를 하나도 늘리지 않고 한 단계 진행할 수 있으므로, 같은 level의 다른 노드로 나아갔을때와 비교하여 경로의 길이가 줄면 줄었지 최소한 더 늘어나지는 않게된다.

   따라서 인접 노드 탐색할 때 가중치가 0인 노드부터 우선 방문하도록 설계하면, BFS의 '이미 방문했던 노드는 방문하지 않고 너비를 우선적으로 탐색하는 로직'대로 최단 경로를 찾을 수 있게 된다.

배운 점, 어려웠던 점

• 다익스트라로는 어렵지 않게 풀었는데, BFS로는 정확하게 풀어내지는 못했다. 다른 사람 풀이를 참고하여 BFS로 풀어보았는데, 그 과정에서 다익스트라와 BFS의 개념 간에 헷갈리는 부분들이 생겼고, 둘의 차이점을 더 면밀히 공부했다. 기초가 탄탄해야함을 절실히 느꼈다.