알고리즘 유형 : 다익스트라 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) 풀이 요약 (다익스트라 풀이)
-
이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다.
0부터 10만까지의 노드가 있고, 모든 노드는 0이상 10만 이하의 범위 안에서 -1, +1, x2의 노드와 간선으로 연결이 되어 있는 그래프이고 간선의 가중치는 0 또는 1이다.
가중치가 모두 0 또는 양수이고, 특정 노드에서 특정 노드까지의 최단 경로 가중치를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다.
- 기존의 다익스트라 형태에서 조금 다른 점은, 그래프 간선 정보가 따로 주어지는게 아니라, 현재 노드에 대해 -1, +1, x2를 인접 노드로 정의하고 순회하면 된다. 이를 위해 제너레이터를 사용한다.
-
이 때 인접 노드 중 범위를 벗어나는 경우를 조건문으로 걸러줘야한다.
마지막에 K 노드의 최단 경로 가중치 값을 리턴하면 끝이다.
SOLVE 2 풀이 요약 (BFS 풀이)
- BFS를 약간 변형한 풀이이다.
-
BFS는 인접 노드들을 너비 우선 탐색하면서 최단 경로를 찾는 알고리즘이다.
다만 이 문제는 0과 1의 가중치가 있는 그래프가 대상이기 때문에, BFS를 사용하려면 약간의 변형을 생각해봐야한다.
우선 BFS는 가중치가 없는 그래프에서 가장 먼저 목표 노드를 찾았을 때, 그 때까지의 경로가 최단 경로임이 보장된다.
이 문제에서 너비 우선 탐색했을 때 최단 경로임을 보장하려면, 그래프의 어떤 노드의 인접 노드를 탐색할 때 가중치가 0인 노드부터 먼저 방문해야한다.
서로 같은 level에 위치한 노드들 중에서, 가중치가 0인 노드는 가중치를 하나도 늘리지 않고 한 단계 진행할 수 있으므로, 같은 level의 다른 노드로 나아갔을때와 비교하여 경로의 길이가 줄면 줄었지 최소한 더 늘어나지는 않게된다.
따라서 인접 노드 탐색할 때 가중치가 0인 노드부터 우선 방문하도록 설계하면, BFS의 '이미 방문했던 노드는 방문하지 않고 너비를 우선적으로 탐색하는 로직'대로 최단 경로를 찾을 수 있게 된다.
배운 점, 어려웠던 점
- 다익스트라로는 어렵지 않게 풀었는데, BFS로는 정확하게 풀어내지는 못했다. 다른 사람 풀이를 참고하여 BFS로 풀어보았는데, 그 과정에서 다익스트라와 BFS의 개념 간에 헷갈리는 부분들이 생겼고, 둘의 차이점을 더 면밀히 공부했다. 기초가 탄탄해야함을 절실히 느꼈다.
