[BOJ 1697] 숨바꼭질

문제 요약

문제 요약
수빈이의 수에서 동생의 수로 가기 위해 1초가 걸리는 3가지 행동이 있다.
1. 현재 수에서 -1을 한다
2. 현재 수에서 +1을 한다
3. 현재 수에서 x2를 한다
수빈이의 수에서 동생의 수까지 갈 수 있는 가장 빠른 시간이 몇 초 후인지 구하시오.
입력
N K (수빈이의 위치, 동생의 위치)
출력
최소 시간을 출력한다.

풀이

얼핏보면 완전이진트리처럼 보일 수 있지만, 트리가 아니라 그래프이다.
노드와 노드 사이의 최단 거리를 구하기 위해 BFS(너비 우선 탐색)을 쓰면 된다.
BFS는 방문 여부를 잘 검사해야 한다. (안 그러면 무한 루프에 빠질 수 있다.)
check라는 배열을 통해 -1이라면 방문하지 않은 노드, 0 이상이면 방문한 노드로 구별할 것이다.
한번 BFS를 돌릴 때 이전 check값에 1을 더한 값을 다음 노드에 넣는 방식으로 최단 시간을 구축한다.

BFS를 하기 위해 준비해야 할 것은 무엇인가?

점의 위치는 0부터 100,000까지이므로 check배열을 -1로 0부터 100000까지 초기화 시켜준다.
BFS를 할 때 다음 방문 노드를 저장하기 위한 Queue도 선언한 다음, 시작지점인 N을 먼저 넣는다.
그리고 시작지점의 check값을 0으로 초기화한다.

check = [-1 for _ in range(100001)]
q = queue.Queue()
q.put(N); check[N] = 0

BFS는 어떻게 진행해야 할까?

1. Queue에 있는 다음 방문 노드를 꺼낸다.
2. 그 노드의 check값에 1을 더한 값을 다음노드의 check값에 넣도록 check_num이라는 변수에 저장한다.
3. -1, +1, x2방향으로 탐색을 진행한다.
   3-1. num-1, num+1, numx2를 Queue에 넣는다.
   3-2. check[num-1 or num+1 or numx2] = check_sum
   3-3. num-1, num+1, numx2이 K라면 while문을 빠져나온다.

주의해야 할 점

N과 K가 같은 경우를 생각해야 한다.
-1같은 경우, num이 0이면 안 된다.
+1같은 경우, num이 100,000이면 안 된다.
x2같은 경우, num이 0이거나 50,000보다 크면 안 된다.

결과 코드

import sys, queue
input = sys.stdin.readline

N, K = map(int,input().split())
check = [-1 for _ in range(100001)]
q = queue.Queue()
q.put(N); check[N] = 0

if N == K:
    print(0)
else:
    while True:
        num = q.get()
        check_num = check[num] + 1

        if num != 0 and check[num-1] == -1:
            q.put(num-1)
            check[num-1] = check_num
            if num-1 == K:
                break

        if num < 100000 and check[num+1] == -1:
            q.put(num+1)
            check[num+1] = check_num
            if num+1 == K:
                break
        
        if num != 0 and num*2 <= 100000 and check[num*2] == -1:
            q.put(num*2)
            check[num*2] = check_num
            if num*2 == K:
                break

    print(check[K])

반성할 점

처음에 완전이진트리로 푸는 것이라 생각했고, 0의 경우를 생각하지 않아 무한 루프가 걸려 많은 시행착오를 겪어야 했다...

문제가 풀리지 않을 때 차분하게 큰 부분부터 다시보는 습관을 가져야 할 것 같다...