[백준 12851] 숨바꼭질 2

 

문제

---

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

12851번: 숨바꼭질 2

 

나의 풀이

---

BFS를 사용하여 풀었다.

걸린 시간 외에도 경우의 수를 카운트해야 하므로 방문 체크를 일반적인 방식으로 하면 안된다. 일반적인 경우처럼 방문한 곳은 다시 가지 않도록 하면 K까지의 경우의 수는 언제나 1이 되기 때문이다.

따라서 visit 체크를 2가지 경우로 나누어주어야 한다.(아래 코드 참고)

 

코드

---

# https://www.acmicpc.net/problem/12851

from collections import deque

N, K = map(int, input().split())
visit = [[-1,0] for _ in range(100001)] #[걸린시간, 경우의 수]
q = deque()
q.append(N)   #(pos, time)
visit[N][0] = 0
visit[N][1] = 1
while q:
    x = q.popleft()
    for nx in [x-1, x+1, 2*x]:
        if 0<= nx <= 100000:
            # 첫방문이라면
            if visit[nx][0] == -1:
                visit[nx][0] = visit[x][0] + 1
                visit[nx][1] = visit[x][1]
                q.append(nx)
            # 첫방문은 아니지만 최소시간이라면
            elif visit[nx][0] == visit[x][0] + 1:
                visit[nx][1] += visit[x][1]

print(visit[K][0])
print(visit[K][1])