[BOJ] 13549. 숨바꼭질 3 Python

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

13549번: 숨바꼭질 3

 

 

1. 해결방법

DFS인줄 알았으나, 재귀에러에 두들겨 맞고 BFS로 풀었다.

왜 bfs인지는 문제를 풀면서 느낌;;


1. 현재 인덱스 위치랑 time을 q에 append 한다. 
2. x * 2, x - 1, x + 1의 경우에는 가중치가 0 그리고 1로 다르므로 bfs를 이용하여 3가지 모두 탐색을 한다.
3. 유효성 검사와 방문체크도 하고, 새로운 인덱스 위치와 가중치인 time의 값을 갱신해서 q에 append한다.

주의할점) x * 2, x - 1, x + 1 순서로 for문을 탐색해야 정답이 나온다.
예를 들면, 4 6을 입력받았을 때, 4 -> 3 -> 6 의 방식으로 가중치가 1이 나오게 된다.

하지만, 여기서 x * 2, x + 1, x - 1로 한다면???
6에 도달한 가중치가 2가 되어버려서 유효성 검사때문에 최소 가중치의 값을 얻거나 갱신하지도 못하고 2로 고정되어버린다.

반례는 직접 디버깅을 하길 권장.

 

 

2. 정답코드

import sys
from collections import deque

input = sys.stdin.readline


N, K = map(int, input().split())
chk = [False] * 100001


def bfs():
    q = deque()
    q.append((N, 0))

    while q:
        idx, time = q.popleft()

        if idx == K:
            return time

        for n in (idx * 2, idx - 1, idx + 1):
            if 0 <= n <= 100000 and chk[n] == False:
                chk[n] = True
                if n == idx * 2:
                    q.append((n, time))
                else:
                    q.append((n, time + 1))

chk[N] = True
print(bfs())