백준 1697 숨바꼭질

숨바꼭질

계획

• BFS로 풀어야 할 것 같았음.

import sys
from collections import deque

N, K = map(int, input().split())

visited = [False for _ in range(100001)]

def bfs(start, end):
    queue = deque([[start, 0]])
    while queue:
        v = queue.popleft()
        if v[0] == end:
            return v[1]
        if visited[v[0]] or v[0] < 0 or v[0] > 100000:
            continue
        else:
            visited[v[0]] = 1
            if v[0] < 100000:
                queue.append([v[0] + 1, v[1] + 1])
            if v[0] >= 0:
                queue.append([v[0] - 1, v[1] + 1])
            if v[0] % 2 == 0:
                queue.append([v[0] // 2, v[1] + 1])
print(bfs(K, N))

• BFS로 풀어야 할 것 같아서 풀다가 아닌가 해서 DFS로 풀다가 진짜 아닌거 같아서 BFS로 풀게 됨
• 횟수 표현하는게 더 좋은 방법이 있을 것 같은데..
• 무작정 BFS 했더니 계속 메모리 초과가 떠서 최대한 계산을 줄이기로 머리를 씀
• 방문했던 곳에 대한 가지는 이미 큐에 들어가있을 것이므로 추가하지 않음.
• 처음에는 시작 위치부터 끝 위치를 찾아가는 방식으로 했는데, 끝에서 시작 위치를 찾아가면 홀수인 경우를 제할 수 있어서 방식을 바꿈