[백준] 숨바꼭질 3 - Python

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

13549번: 숨바꼭질 3

아이디어

• bfs로 탐색을 시작
• +1과 -1은 cnt를 증가시키고 *2는 그냥 위치만 이동
• *를 할 때 0이 되면 무시 (무한반복방지)
• k에 도착했을 때 k의 cnt 출력

구현(99% 실패)

from collections import deque

def bfs(N):

    visited = [0] * 100001
    q = deque()
    q.append(n)

    while q:
        now = q.popleft()
        if now == k:
            return visited[now]

        for i in (now + 1, now - 1, now * 2) :

            if 0 <= i < 100001:
                if visited[i] == 0:
                    if i == now * 2 and i != 0:
                        visited[i] = visited[now]
                        q.appendleft(i)
                    else:
                        visited[i] = visited[now] + 1
                        q.append(i)


n, k = map(int, input().split())
print(bfs(n))

틀린 원인 분석

• 도저히 틀린 원인을 찾을 수 없음
• 찾아보자..

정답코드

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
q = deque()
q.append(N)
visited = [-1 for _ in range(100001)]
visited[N]=0

while q:
    s=q.popleft()
    if s == K:
        print(visited[s])
        break
    if 0 <= s-1 < 100001 and visited[s-1]==-1:
        visited[s-1]=visited[s]+1
        q.append(s-1)
    if 0 <= s*2 < 100001 and visited[s*2]==-1:
        visited[s*2]=visited[s]
        q.appendleft(s*2)
    if 0 <= s+1 < 100001 and visited[s+1]==-1:
        visited[s+1]=visited[s]+1
        q.append(s+1)

흠..?

마무리

• 흠 내 코드랑 복잡도도 똑같은데 왜 다른 결과가 나온지 아직 모르겠음..
• 뭐지 ㅇㅅㅇ