[백준 2024/10/29] 13549번 숨바꼭질 3

1. 문제

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

 

2. 접근 방법

BFS로 문제를 접근하였다. 이를 위해서 deque를 이용하였다.

queue에서 먼저 pop이 된 것이 동생의 위치를 나타낸다면, 그것이 가장 빠르게 동생에게 접근하는 경우라고 판단하였다.

 

또한 memoization을 이용해 주어, 해당 위치에 접근했을 때의 cnt를 list에 저장해 주었다. 만약 cnt가 더 작다면, 해당 memoization을 갱신해주고, 해당 위치에서 방문 가능한 경우들 x-1, x+1, 2*x에 대해서 위치를 deque에 넣어주었다.

 

하지만, 순서가 중요했다. 우선순위가 있는 접근들을 먼저 queue에 넣어주어야 했다.

우선순위는 2*x, x-1, x+1이다.

 

2*x의 경우 직관적으로 우선순위를 주어야 함을 알지만, x-1의 경우엔 조금 모호하였다.

 

https://www.acmicpc.net/board/view/127319

 

위 질문게시판의 게시글을 통해 그 이유를 알 수 있었다.

 

4 -> 3 -> 6 #1번
4 -> 5 -> 6 #2번

 

마이너스를 할 경우, 곱셈을 통해 계산 횟수를 줄일 수 있기 때문이다.

 

추가적으로, 0 <= 이라는 조건을 잊어 indexError가 발생하기도 하였다.

3. 코드

import sys
from collections import deque


def bfs(x, y):
    visited = [sys.maxsize] * 100001
    dq = deque()

    dq.append((x, 0))
    while dq:
        length = len(dq)

        for _ in range(length):
            x, cnt = dq.popleft()
            if visited[x] <= cnt:
                continue

            visited[x] = cnt

            if x == y:
                return cnt

            if 0 <= x*2 <= 100000 and visited[x*2] == sys.maxsize:
                dq.append((x*2, cnt))

            if 0 <= x-1 <= 100000 and visited[x-1] == sys.maxsize:
                dq.append((x-1, cnt+1))

            if 0 <= x+1 <= 100000 and visited[x+1] == sys.maxsize:
                dq.append((x+1, cnt+1))


if __name__ == "__main__":
    x, y = map(int, input().split())
    print(bfs(x, y))