🥚문제

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

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

🥚입력/출력

🍳코드

# 출처: https://jaimemin.tistory.com/582
import sys
input = sys.stdin.readline
from collections import deque

def bfs(N, K):
    visited = [False]*100001
    visited[N] = True
    q = deque([(N, 0)])

    # 찾을 수 있는 가장 빠른 시간
    min_time = float('inf')
    # 가장 빠른 시간으로 찾는 방법
    min_time_ways = 0

    while q:
        # q에서 꺼낼 때! 방문 표시를 해주는 것이 핵심이다
        x, time = q.popleft()
        visited[x] = True

        if x == K:
            if time < min_time:
                min_time = time
                min_time_ways = 1
            elif time == min_time:
                min_time_ways += 1
            continue
        
        if 0 <= x - 1 < 100001 and not visited[x-1]:
            q.append((x-1, time + 1))
        
        if 0 <= x + 1 < 100001 and not visited[x+1]:
            q.append((x+1, time + 1))
        
        if 0 <= x * 2 < 100001 and not visited[x*2]:
            q.append((x*2, time + 1))
    
    return min_time, min_time_ways



N, K = map(int, input().split())
min_time, min_time_ways = bfs(N, K)
print(min_time)
print(min_time_ways)

🧂아이디어

BFS

참고: https://jaimemin.tistory.com/582

• 다른 숨바꼭질 문제와 달리, 가장 빠른 시간과 함께, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지도 함께 출력해줘야 하는 문제이다.

• 대표적인 반례는 아래와 같다.
  N = 1, K = 4일 때 가장 빠른 시간은 2, 가장 빠른 시간으로 찾는 방법은 2가지여야 한다.

  • 1 -> 1 + 1 -> (1 + 1) * 2
  • 1 -> 1 * 2 -> (1 * 2) * 2

• 기존의 BFS에서는 새로운 위치 (nr, nc)를 방문할 수 있을 때, visited[nr][nc] = True, q.append((nr, nc))와 같은 방식으로 방문 표시 + 큐에 삽입해준다.

• 하지만, 위 방식으로 하면 새로운 위치 (nr, nc)를 방문할 수 있는 방법이 여러개가 있다고 할 때 그 방식들 중 하나가 먼저 방문 표시를 해버리면 다른 방식으로는 (nr, nc)를 방문할 수 없게 된다.

• 따라서, 기존의 BFS와 달리 q에 append 해줄 때 방문 표시를 해주는 것이 아니라 q에서 pop해줄 때 방문 표시를 해줌으로써 위 문제를 해결한다.