[python] 백준 12851 숨박꼭질 2

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

12851번: 숨바꼭질 2

 

문제 해결

• 가장 빠르게 N에서 K로 가는 길을 찾으면 된다.
• 이 때는 BFS를 이용하는 것이 좋다.
• 이동 했는데 이미 방문한 적이 있으면 더 빠르게 이동 할 수 있는 방법이 존재하는 것이므로 pass한다.
• ways를 통해 이동할 수 있는 방법이 여러개면 여러개가 있다는 것을 value 값을 통해 더해주면서 이동할 수 있다.

CODE

from collections import deque

def bfs(N, K):
    # 방문 여부와 시간을 저장하는 배열
    max_size = 100001
    visited = [-1] * max_size
    # 방법의 수를 저장하는 배열
    ways = [0] * max_size
    
    # 초기 위치를 큐에 넣음
    queue = deque([N])
    # 초기 위치의 방법의 수는 1
    ways[N] = 1
    visited[N] = 0
    
    while queue:
        cur_pos = queue.popleft()
        
        # 가능한 이동 경로
        for next_pos in [cur_pos - 1, cur_pos + 1, cur_pos * 2]:
            # 범위 내에 있고, 아직 방문하지 않았거나(visited[next_pos] == 0) 
            # 현재 위치에서 1초 후에 도달할 수 있는 경우(visited[next_pos] == visited[cur_pos] + 1)
            if 0 <= next_pos < max_size and (visited[next_pos] == -1 or visited[next_pos] == visited[cur_pos] + 1):
                # 처음 방문하는 경우에만 큐에 추가
                if visited[next_pos] == -1:
                    queue.append(next_pos)
                    visited[next_pos] = visited[cur_pos] + 1
                
                # 방법의 수를 누적
                ways[next_pos] += ways[cur_pos]
    
    # 가장 빠른 시간과 방법의 수 반환
    return visited[K], ways[K]

if __name__=='__main__':
    N, K = map(int, input().split())
    # 출력
    time, count = bfs(N, K)
    print(time)
    print(count)