[백준-파이썬] 12851: 숨바꼭질 2

문제 보러 가기!

평범한 BFS 문제에서 조금 더 생각해야 했다..

dq에는 위치, 얼마나 걸렸는지를 가지고 있는다.
앞으로 걷고, 뒤로 걷고, 순간이동하는 경우를 범위, 방문 체크한 후에 dq에 넣는다.

일단 N이 0일 때는 곱하기 2해도 0이고, -1은 해도 점점 멀어지는 거니까 괜히 시간만 든다. N이 0일 때는 일단 무조건 한 칸 앞으로 가야 하니까, dq에 (N+1, 1)을 넣고 시작한다.

틀리다가 질문 게시판의 반례!!를 보고 문제를 알았다. dq에 넣을 때 방문 체크를 하면 안되고, 뺄 때 방문 체크를 해야 한다! 1 10의 경우에 1->2->4->5->10으로 가는 게 젤 빨리 가는 것인데, 1에서 2로 갈 때 걸어서 갈 수도, 순간 이동해서 갈 수도 있다. dq에 넣을 때 방문 체크를 하면, 둘 중에 한 가지 경우를 dq에 못 넣게 된다.

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
visited = [False] * 200001  # 중복 검사


def sol():
    find_method_cnt = 0
    short_time = -1

    dq = deque()

    dq.append((N, 0))
    if N == 0:  # N이 0이면 -1로는 가면 안되고, *2해도 어차피 0이니까, +1로만 갈 수 있어서 따로 해줌
        dq.append((N + 1, 1))  # 아래에서 0 < tmp 조건이 있어서 미리 먼저 빼둠

    while dq:
        tmp, cnt = dq.popleft()

        visited[tmp] = True  # 이제 방문했다고 체크하기

        if tmp == K:  # 수빈이가 동생을 찾은 경우 !
            if short_time == -1:  # 맨 처음 찾은 것이면
                short_time = cnt

            if short_time == cnt:  # 최소 시간으로 찾았으면
                find_method_cnt += 1
                continue

            else:  # 더 이상 봐도 찾는 시간 더 오래 걸리는 것만 나올 것이니까.
                break

        if 100000 >= tmp > 0:  # N이 0인 경우는 위에서 처리. N 말고 tmp가 0이면 고려하지 않아야 함. (tmp가 0인 건 1에서 -1로 온 경우 뿐인데, 0이 갈 길은 +1뿐.. 그럼 어차피 자기가 왔던 길을 가는 거니까)
            if visited[tmp - 1] == False:
                dq.append((tmp - 1, cnt + 1))  # 앞으로 걷기
            if visited[tmp + 1] == False:
                dq.append((tmp + 1, cnt + 1))  # 뒤로 걷기
            if visited[tmp * 2] == False:
                dq.append((tmp * 2, cnt + 1))  # 순간이동

    return short_time, find_method_cnt


fast_time, find_cnt = sol()
print(fast_time)
print(find_cnt)