[백준] 1697번 숨바꼭질 - 파이썬(Python)

문제 (링크)

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

1697번: 숨바꼭질

 

나의 풀이

from collections import deque
N, K = map(int, input().split())
visited = [False] * 100001

def bfs(v):
	count = 0
    q = deque()
    q.append([v, count])
    
    while q:
    	x = q.popleft()
        current = x[0]
        count = x[1]
        
        if visited[current] == False:
        	visited[current] = True
            
            if current == K:
            	return count
                
            count += 1
            
            if current * 2 <= 100000:
            	q.append([current*2, count])
            
            if current + 1 <= 100000:
            	q.append([current+1, count])
			
            if current - 1 >= 0:
            	q.append([current-1, count])
	
    return count

print(bfs(N))

접근 방법 및 코드 설명

처음에는 전형적인 DP를 사용할 수 있다고 판단하여 입출력 예시에 있던 5와 17의 경우에 대한 경우의 수를 나열해봤지만, 음수로 움직이는 경우가 있기 때문에 다른 방법이 필요하다고 생각했다.

 

결국에 떠올린 건 현재 위치에서 움직일 수 있는 모든 방향들에 대하여 bfs를 실행하는 것이었는데, 오랜만에 알고리즘 문제를 풀려니 생각보다 머리가 안 돌아가서 살짝 고생했다.

 

특히, count를 어떻게 세어줘야 좋을 지 몰라서 이곳 저곳 찾아봤는데 단순히 deque에 현재 값과 함께 넣어주는 방식이 있었다.

 

이 정도만 떠올리면 큰 어려움 없이 풀 수 있는 문제였다.