[BOJ] 백준 1697. 숨바꼭질

✅ 난이도

실버1

✅ 문제

문제링크

✅ 개념

• BFS
  주로 최단 경로 문제에서 활용 (두 정점 간의 최단 경로 찾기)
  * deque와 queue의 차이
  queue는 한쪽으로만 입력하고, 반대쪽으로만 출력 가능
  deque는 양쪽으로 입출력 가능
• DFS
  모든 노드를 다 찾아보는 문제에서 활용 (미로 찾기 등)
• 방문처리의 중요성
  방문처리 안해주면 중복탐색이 발생해서 메모리 초과가 뜸

✅ 풀이

1. 이 문제의 경우는 최단경로를 찾는 것이기에 BFS (큐 사용)을 통해 풀이했다.
2. 정점 x가 정점 x+1, x-1과 x* 2 랑 연결되어 있는 그래프 형태임

✅ 코드

from collections import deque
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
# 방문 노드 추가 (0부터 100000이면 100001개임)
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))