백준: 12851 숨바꼭질 2

숨바꼭질 시리즈

• 숨바꼭질
• 숨바꼭질 2
• 숨바꼭질 3
• 숨바꼭질 4

 

문제

12851번: 숨바꼭질 2

 

문제 풀이

 앞서 다룬 1697 숨바꼭질 문제에서 조건이 추가된 문제이다. 수빈이의 위치가 5, 동생의 위치가 17일 때 BFS를 통해 탐색해보면 위의 그림과 같이 가장 빠른 시간인 4초에 찾을 수 있는 방법은 2가지 라는 것을 알 수 있다.

 즉, 이전 문제는 단순히 몇 초만에 찾을 수 있는가?를 묻는 문제였으면 가장 빠른 시간에 찾는 방법은 몇 가지인지를 추가적으로 찾는 문제이다. 

 

코드

from sys import stdin
from collections import deque


def bfs(start):
    q = deque([start])

    while q:
        cur_loc = q.popleft()

        for next_loc in (cur_loc - 1, cur_loc + 1, cur_loc * 2):
            if 0 <= next_loc < MAX_LOC:
                if not check[next_loc][VISIT]:
                    check[next_loc][VISIT] = check[cur_loc][VISIT] + 1
                    check[next_loc][WAY] = check[cur_loc][WAY]
                    q.append(next_loc)
                elif check[next_loc][VISIT] == check[cur_loc][VISIT] + 1:
                    check[next_loc][WAY] += check[cur_loc][WAY]

    return check[k]


if __name__ == '__main__':
    MAX_LOC = 100001
    VISIT, WAY = 0, 1
    n, k = map(int, stdin.readline().split())
    check = [[0, 0] for _ in range(MAX_LOC)]
    check[n][WAY] = 1
    time, way = bfs(n)
    print(time, way, sep='\n')

1697 숨바꼭질 문제와 다른 점이 있다면, 해당 위치까지 방문하는데 걸린 시간과, 만약 방문한 위치라면 해당 위치를 방문하는데 걸린 시간과 현재 위치를 방문하는데 걸린 시간이 같은 경우, 찾을 수 있는 방법을 추가하면 된다.