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

💡문제

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

💡풀이

기존 숨바꼭질에서, 역추적만 추가된 문제.
bfs 중에서 상당히 간단한 편이긴 한데, 2가지 방법으로 풀었다.
하나는 우선순위 큐 자료구조를 이용한 BFS,
다른 하나는 큐 자료구조 + BFS + 재귀로 풀었다.

풀이 방법은 다음과 같았다.

우선순위 큐 + BFS를 사용한 경우
1. heapq에 저장한 것: (걸린 시간, 현재 위치, [지금까지 갔던 곳])
2. 계속해서 pop된 값이 가리키는 현재 위치가 목표 지점과 같은지를 비교하며, bfs 수행.

큐 + BFS + 재귀
1. bfs를 수행하되, 기존에 마지막에 갔던 위치를 저장하기 위해 dp를 2차원 배열로 생성.
2. 똑같이 bfs 수행.
3. 현재 위치와 목표 지점이 같아지면 재귀를 통해 역추적 실행.

💡코드

1번 코드

import heapq

def bfs(now, target):
    if now == target:
        return 0, [now]
    elif now > target:
        return now - target, [i for i in range(now, target - 1, -1)]
    else:
        heapq.heappush(q, [0, now, [now]])
        while q:
            cnt, pos, trace = heapq.heappop(q)
            for i in [pos * 2, pos - 1, pos + 1]:
                if i == target:
                    return cnt + 1, trace + [i]
                if 0 <= i <= 100000 and not dp[i]:
                    dp[i] = True
                    heapq.heappush(q, [cnt + 1, i, trace + [i]])

if __name__ == "__main__":
    N, K = map(int,input().split())
    dp = [False] * (100000 + 1)
    q = []
    res, trace = bfs(N, K)
    print(res)
    print(*trace)

2번 코드

from collections import deque
import sys
def check(now, target, res):
    if now == target:
        return res[::-1]
    else:
        res.append(dp[target][1])
        return check(now, dp[target][1], res)


def bfs(now, target):
    if now == target:
        return 0, [now]
    elif now > target:
        return now - target, [i for i in range(now, target - 1, -1)]
    else:
        dp[now][0] = 0
        while q:
            pos = q.popleft()
            for i in [pos * 2, pos + 1, pos -1]:
                if dp[target][0] != -1:
                    return dp[target][0], check(now, target, [target])
                    break
                if 0 <= i <= 100000 and dp[i][0] == -1:
                    dp[i][0] = dp[pos][0] + 1
                    dp[i][1] = pos
                    q.append(i)

if __name__ == "__main__":
    sys.setrecursionlimit(10000)
    N, K = map(int, input().split())
    dp = [[-1,-1] for _ in range(100001)]
    q = deque()
    q.append(N)
    res1, res2 = bfs(N, K)
    print(res1)
    print(*res2)

결과

결론은, 2번 방법이 좀 더 시간복잡도 면에서 효율적이게 나왔다.
개인적으로도 꽤나 만족스럽게 풀었던 문제.
결과는 다음과 같다.

1번 방법 결과

2번 방법 결과