[백준] (실패) 13913 숨바꼭질 4

Hyun·2025년 5월 3일

백준

목록 보기

95/96

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

예제 입력 1

5 17

예제 출력 1

4
5 10 9 18 17

예제 입력 2

5 17

예제 출력 2

4
5 4 8 16 17

풀이

이 문제를 처음 보고, 이전에 푼 문제인줄 알았는데 내가 풀었던 문제는 1697 숨바꼭질 문제였다.

어쨌든, 이 문제를 풀면서 bfs 풀이를 생각해냈고, 아래와 같이 풀었다.

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

n, k = map(int, input().split()) # 수빈이의 위치, 동생의 위치

def bfs():
    queue = deque()
    # 초기값
    queue.append([0, n])
    
    while queue:
        sub_arr = queue.popleft()
        cnt, cur = sub_arr[0], sub_arr[-1]
        # 동생의 위치에 도달한 경우
        if cur == k:
            print(cnt)
            print(' '.join(map(str, sub_arr[1:])))
            break
        # 그렇지 않은 경우
        for _ in range(2):
            sub_arr[0] += 1 # 횟수 증가
            if cur + 1 > k:
                queue.append(sub_arr + [cur-1])
            else:
                queue.append(sub_arr + [cur+1])
                queue.append(sub_arr + [cur-1])
                queue.append(sub_arr + [cur*2])

bfs()

위 방법으로 풀이 시에, bfs 특징인 가장 빨리 도착했을 때 while 문을 빠져나오게 된다. 그러나, 위 풀이의 가장 큰 문제는 bfs 시 이미 방문했던 좌표에 대해서도 또 다시 bfs 탐색 대상이 될 수 있고, 동시에 해당 좌표까지의 누적 경로가 담긴 배열을 큐에 넣는다는 것이다.

[기존 문제]

방문한 좌표 다시 방문할 수 있음 -> 불필요 작업 발생

(위의 문제에 더해) 큐에 누적 경로 배열이 매번 쌓임 -> 메모리 과다 사용 발생

따라서 우리는 방문처리를 함과 동시에, 누적 경로를 관리하는 방법을 택해야 한다. 생각해보면 방문하지 않은 좌표만을 방문한다면, 하나의 좌표에 대해 기록하게 되는 정보는 한가지 밖에 없기 때문에 우리는 방문 처리를 위한 배열은 한 개만 있으면 된다.

첫 번째 해결 방법으로는 튜플을 사용하여 방문 처리와, 누적 경로를 동시에 관리하는 방법이다. visited 배열에 현재 좌표까지 도착하기까지 걸린 이동 횟수와, 직전 좌표의 값을 튜플로 기록했다.

방문 횟수와 직전 좌표를 튜플로 한번에 관리

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

n, k = map(int, input().split())
visited = [0 for _ in range(100001)] # 위치 범위: 0 ~ 100000

# bfs 로 풀되, 방문한 좌표인 경우 bfs 수행 X
def bfs():
    queue = deque()
    queue.append(n) # 현재 위치
    visited[n] = (0, n) # 위치 n 에 도착할때까지 걸린 시간, 직전 위치
    
    while queue:
        cur = queue.popleft()
        # 현재 위치가 k 인 경우
        if cur == k:
            break
        # 그렇지 않은 경우
        for np in (cur+1, cur-1, cur*2):
            if np >= 0 and np <= 100000 and visited[np] == 0:
                queue.append(np)
                visited[np] = (visited[cur][0]+1 , cur)

bfs()

# 역추적
temp = k
ans = [k]
while True:
    ans.append(visited[temp][1])
    if visited[temp][1] == n:
        break
    temp = visited[temp][1]

print(visited[k][0])
if n == k:
    print(' '.join(map(str, [n])))
else:
    print(' '.join(map(str, reversed(ans))))

두 번째 방법으로는 방문 횟수와, 직전 좌표를 각각의 배열에서 관리하는 것이다. 뭐가 낫다기보다는, 유동적으로 사용하면 될 것 같다.

방문 횟수와 직전 좌표를 각각의 배열로 관리

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

n, k = map(int, input().split())
visited = [-1 for _ in range(100001)]
parent = [0 for _ in range(100001)]

def bfs():
    queue = deque()
    queue.append(n)
    visited[n] = 0
    parent[n] = n
    
    # k 위치까지 찾아감, 도착하면 빠져나옴 (parent 배열 완성됨)
    while queue:
        cur = queue.popleft()
        if cur == k:
            break
        
        for np in (cur-1, cur+1, cur*2):
            # visited 초기화를 0으로 하고, 여기서 visited[np] == 0 으로 하면 
            # 좌표 n 을 이미 방문했음에도 방문하지 않은 것처럼 취급됨
            if np >= 0 and np <= 100000 and visited[np] == -1: 
                queue.append(np)
                visited[np] = visited[cur] + 1
                parent[np] = cur
                
    # parent 배열 추적
    temp = k
    ans = []
    while True:
        ans.append(temp)
        if temp == parent[temp]:
            break
        temp = parent[temp]
        
    print(visited[k])
    print(' '.join(map(str, reversed(ans))))

bfs()