문제 유형 : BFS, 역추적
난이도 : 골드 4
https://www.acmicpc.net/problem/13913
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
예전에 풀었었다.
점 N을 시작노드, K를 도착노드로 보고
X+1, X-1 , 2*X 를 간선으로 보고 최소 거리(시간) 을 구하는 BFS 문제였다.
1697번: 숨바꼭질 이 위 풀이였고
또 하나 숨바꼭질 문제 더 풀었었는데
13549번: 숨바꼭질 3 문제였다.
이는 X+1과 X-1은 마찬가지로 가중치가 1이었지만 2X 간선의 가중치가 0으로 deque를 사용해서, 0초 이동(2)은 appendleft() 1초 이동(±1)은 append() 이렇게 해서 0초 이동을 우선적으로 처리하도록 했었다.
이번에 풀 문제는 1697번 + 역추적으로 최소시간을 들여서 가는 경로까지 출력해주면 되는 문제이다.
BFS가 가물가물해서 다시 리마인드해본다.
BFS가 뭐냐면?
그래프에서 시작 노드에서 가까운 노드부터 차례대로 탐색하는 방법.
큐(queue)를 써서 방문할 순서를 관리.
로직 흐름
-
큐에 시작 노드를 넣고, visited를 기록해둔다.
(중복 방문 방지) -
큐가 빌 때까지 아래를 반복한다:
- 큐에서 앞쪽 노드를 꺼낸다. → current
- current에서 갈 수 있는 이웃 노드들을 확인한다.
- 그 이웃 노드가 아직 방문 전이면:
- 큐의 뒤쪽에 넣는다.
- visited로 체크한다.
(추가 정보가 필요하면 prev에 어디서 왔는지도 기록) -
이렇게 하면 시작점에서 가까운 것부터 탐색되므로,
가장 먼저 목적지에 도착했을 때가 최단 거리가 된다.
역추적 로직은
prev[] 배열에 prev[i]라면 i가 되기전 값을 넣어주고
path 배열을 선언해준뒤
마지막 도착노드를 만났을 때, 그 도착노드 값부터 path에 넣고
prev배열에서 이전 값들을 꺼내서 current 값에 넣고 current 값이 초기값인 -1이 될때까지 path에 넣고, current 값을 다시 prev배열에서 이전값으로 바꿔주는 과정을 반복하여 마지막 path 배열을 뒤집어준 뒤 출력해준다.
해답 및 풀이
import sys
from collections import deque
input = sys.stdin.readline
def bfs(n, k):
max_pos = 100001 # N의 범위는 100,000 까지라.
visited = [-1] * max_pos # visited[x] => 시작점 N에서 도착위치 k까지 도달하는 데 걸리는 최소 시간
prev = [-1] * max_pos # 어디서 왔는지 저장할 배열
# visited,prev 배열에 -1을 넣어준 이유는 존재하지 않는 값을 명확히 표시하기 위해서
queue = deque()
queue.append(n)
visited[n] = 0 # 출발점 n, 도착점 n -> 0초 걸림
while queue:
now_pos = queue.popleft()
if now_pos == k:
path = []
current = k
while current != -1:
path.append(current) #path 에 current값 k부터 넣음
current = prev[current] #current값을 prev[current] 값, 즉 current 오기 전 값으로 바꿔줌, -1이 될때까지 반복
path.reverse() # 저장된 path를 뒤집어줌.
return visited[now_pos], path
for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
if 0 <= next_pos < max_pos and visited[next_pos] == -1:
visited[next_pos] = visited[now_pos] + 1
prev[next_pos] = now_pos # prev[i]의 값은 i 이전의 무엇이었는 지 저장. now_pos가 5라면 prev[5 다음 pos] = 5
queue.append(next_pos)
N, K = map(int,input().split())
time, path = bfs(N,K)
print(time)
print(*path)