[백준] 1697번 숨바꼭질 BFS

처음에 잘못 푼 코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

def bfs(N, K):
    queue = deque()
    queue.append((N, K, 0))
    while queue:
        n, k, count = queue.popleft()
        if n == k:
            return count
        else:
            queue.append((n+1, k, count+1))
            queue.append((n-1, k, count+1))
            queue.append((2*n, k, count+1))

print(bfs(N,K))

이렇게 풀었을 때 예시 입력을 넣으면 정답은 나오는데, 메모리초과가 나왔다. 방문처리의 중요성을 알게 되었다.

 

BFS

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

def bfs():
    queue = deque()
    queue.append(N)
    while queue:
        x = queue.popleft()
        if x == K:
            return subin[x]
        for nx in (x - 1, x + 1, x * 2):
            if 0 <= nx <= 10 ** 5 and not subin[nx]:
                subin[nx] = subin[x] + 1
                queue.append(nx)

subin = [0] * (10**5 + 1)
print(bfs())

그래서 subin이라는 리스트에 수빈이의 각 위치마다 거리를 표시함으로써 방문처리를 하였다. subin 배열을 처음에 모든 원소를 0으로 초기화했기 때문에, not subin[nx]로 방문했는지 알 수 있다. 그리고 너비 우선 탐색이므로 subin배열의 어떤 인덱스에 처음 접근한 것이 나중에 접근한 것보다 시행한 횟수가 적다.

 

BFS로 풀면 가장 먼저 찾아지는 답이 최적이므로 DFS보다 빠를 수 있다.