[solved.ac 골드5] 12851_숨바꼭질 2 (파이썬, BFS)

제한 사항

문제

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

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

입력

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

출력

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

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

예제

---

나의 풀이

BFS의 시간 복잡도는 보통 O(N + E) 로 표현된다. 노드의 개수 + 간선의 개수인데 이 문제에서 노드의 개수는 최대 100,000개이고, 한 개의 노드에서 뻗을 수 있는 간선이 3개(n-1, n+1, n * 2)라고 했을 때 (물론 100,000을 넘어가는 경우도 있겠지만) 최대 150,000개 정도 존재할 수 있다. (무방향 그래프이기 때문에 2로 나눔) -> 틀린 내용이라면 지적 부탁드립니다!

결국 BFS로 풀었을 때 제한 시간 안에 풀 수 있을 것이라 판단한다.

그런데 이 문제에서는 일반적인 BFS와 약간의 차이가 있다.

바로 방문 처리를 하는 부분이다.

from collections import deque

n, k = map(int, input().split())
visited = [False] * 100001
q = deque([(n, 0)])
fastest, ways = 10 ** 6, 0

while q:
    now, time = q.popleft()
    visited[now] = True # <- 방문 처리를 여기서 함
    if now == k and time <= fastest:
        fastest = min(fastest, time)
        ways += 1
    if time > fastest: break # 큐에는 시간 순으로 들어가므로 fastest보다 커지면 탐색을 종료
    
    for x in (now - 1, now + 1, now * 2):
        if x in range(100001) and not visited[x]:
            q.append((x, time + 1))

print(fastest)
print(ways)

위 코드는 전체 소스 코드이다.

visited를 큐에 넣을 때가 아닌 큐에서 꺼낼 때 처리하는 이유는 큐에 넣을 때 방문 처리를 하게 되면 동생을 찾을 수 있는 경우가 여러 가지가 있음에도 불구하고 최초의 발견 이후로는 방문처리가 되어 있어 아예 큐에 넣지 않게 된다.

큐에서 꺼냈을 때 방문 처리를 하게 되면 일단 큐에는 들어갈 수 있기 때문에 여러 가지 경우를 셀 수 있게 된다.

(물론 이 점 때문에 시간 복잡도가 더 증가할 거라 생각한다)

BFS에서는 Queue를 사용하고, 큐는 선입선출 구조이다. 우리는 큐에 값을 넣을 때 현재 숫자와 시간을 넣는다. 시간은 점차 증가하는 방향으로 넣게 되는데 그 말은 즉 큐에서 데이터를 꺼낼 때 시간이 줄어드는 경우는 없다는 것이다.

그래서 큐에서 뽑은 time이 fastest보다 커지면 더 이상 최소 시간에서 찾을 수 없다는 것이기 때문에 break로 탐색을 종료한다.

그 조건문 하나로 시간과 메모리를 효과적으로 줄일 수 있었다.

 

채점 결과