[백준/BOJ] gold4 - 12851번 숨바꼭질 2 (Python)

▶12851 - 숨바꼭질 2

백준 로고

▶문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

▶입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

▶출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

728x90

▶풀이

숨바꼭질과 비슷한 문제이지만 출력해야 하는 조건이 하나 더 붙은 문제이다.

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

1697번: 숨바꼭질

 

이번에도 역시 bfs문제이다.

요즘 bfs에 빠져서, bfs만 골라서 문제를 풀고 있다.

 

아무튼 count라는 변수도 하나 추가해 주었다.

최소가 되는 모든 경우를 찾아 count를 출력해주어야 하기 때문에 넣었다.

 

뭐 나머지는 비슷해서 큰 어려움 없이 풀었다.

if 0 <= nx <= 100000 and (visit[nx] == -1 or visit[nx] == cnt + 1):

이 부분을 좀 알아두어야 될 거 같다.

그냥 방문하지 않은 경우만 생각해 주었는데, 그렇게 하니 오답이 나왔다.

그래서 다음번 visit[nx]가 cnt + 1인 경우도 추가해 주었다.

 

이 부분은 아무리 생각해도 안 돼서 살짝 검색해 보았다.

사실 아직도 이해가 잘 되지 않는다.

혹시 아시는 분은 댓글로 알려주세요.

from collections import deque


def bfs():
    answer = 999999
    count = 0
    queue = deque([(n, 0)])
    visit[n] = 0
    while queue:
        x, cnt = queue.popleft()
        if answer < cnt:
            continue
        if x == k:
            if answer > cnt:
                answer = cnt

            if answer == cnt:
                count += 1

        for nx in [x - 1, x + 1, x * 2]:
            if 0 <= nx <= 100000 and (visit[nx] == -1 or visit[nx] == cnt + 1):
                queue.append((nx, cnt + 1))
                visit[nx] = cnt + 1

    return answer, count


n, k = map(int, input().split())
visit = [-1 for _ in range(100001)]
answer, count = bfs()

print(answer)
print(count)