[알고리즘] 백준 13549 숨바꼭질 3

백준 13549 숨바꼭질 3

 

이 문제는 단순 BFS문제라고 생각했다.

      

        
        
        
        
      
import sys
import collections
from collections import deque

n,m = map(int,sys.stdin.readline().split())
MAX = 100000
res = [0]*(MAX+1)
res[n] = 1
dq = deque()
dq.append(n)

while dq:
    ex = dq.popleft()
    if ex == m:
        print(res[ex]-1)
        break

	for num in (ex+1,ex-1,ex*2):
        if 0 <= num <= MAX and res[num] == 0:
            dq.append(num)
            if num == ex*2:
                res[num] = res[ex]
            else:
                res[num] = res[ex] + 1

📌 처음 이러한 풀이로 제출했지만 틀렸다. 그래서 30분 정도를 애 먹었다.
키 포인트는 ex의 두 배와 (ex+1,ex-1)의 가중치가 각각 0과 1로 다르다는 것이다. 위의 답은 1과 2가 주어졌을 때 정답이 1로 떨어진다. 그 이유는 ex+1이 먼저 res값을 채우기 때문에 가중치가 없는 ex의 두 배는 res[num] == 0 조건으로 인해 조건에 부합하지 않기 때문이다.

 

      

        
        
        
        
      
import sys
import collections
from collections import deque

n,m = map(int,sys.stdin.readline().split())
MAX = 100000
res = [0]*(MAX+1)
res[n] = 1
dq = deque()
dq.append(n)

while dq:
    ex = dq.popleft()
    if ex == m:
        print(res[ex]-1)
        break

    for num in (ex*2,ex+1,ex-1):  # 여기가 핵심
        if 0 <= num <= MAX and res[num] == 0:
            dq.append(num)
            if num == ex*2:
                res[num] = res[ex]
            else:
                res[num] = res[ex] + 1

📌 그래서 num의 반복문에서 가장 처음을 ex*2로 시작하였다. 이렇게 한다면 1과 2의 오류는 해결할 수 있었다. 그렇지만 이 답 또한 정답이 아니었다.

 

      

        
        
        
        
      
import sys
import collections
from collections import deque

n,m = map(int,sys.stdin.readline().split())
MAX = 100000
res = [0]*(MAX+1)
res[n] = 1
dq = deque()
dq.append(n)

while dq:
    ex = dq.popleft()
    if ex == m:
        print(res[ex]-1)
        break

    for num in (ex*2,ex-1,ex+1):
        if 0 <= num <= MAX and res[num] == 0:
            
            if num == ex*2:
                res[num] = res[ex]
                dq.appendleft(num)
            else:
                res[num] = res[ex] + 1
                dq.append(num)

📌 마지막 Key 포인트는 ex*2를 dq의 뒤에 넣지 말고 맨 앞에 넣는 논리를 적용하는 것이다. 이렇게 한다면 모든 오류를 없앨 수 있다.

 

🆘힌트 이 문제에 대한 힌트를 얻을 수 있는 질문글