[알고리즘] 백준 13913 숨바꼭질 4

백준 13913 숨바꼭질 4

 

 

오답

❌ BFS로 몇 번만에 k에게 도달할 지 구한 뒤 DFS를 구현해서 해당하는 횟수에 해당하는 순간 k값과 같다면 프로그램을 종료하는 로직을 구현했다. 하지만 예상대로 메모리를 너무 차지한다.

import sys
import collections
from collections import deque
sys.setrecursionlimit(1000000)

def DFS(N,x):
    if x == anw:
        if N == k:
            print(anw)
            for t in fin:
                print(t,end=' ')
            sys.exit(0)
        return
    for i in (N*2,N+1,N-1):
        if 0 <= i <= MAX:
            fin.append(i)
            DFS(i,x+1)
            fin.pop()


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

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

fin = [n]
DFS(n,0)

 

 

 

❌ 문제점은 DFS를 쓰는 순간 메모리 용량은 세제곱으로 늘어난다는 것이다.

정답

BFS의 Key 포인트는 deque를 이용하기 때문에 잎사귀에서 바로 뿌리로 직행하는 DFS와 달리 잎사귀 보고 줄기 보고 뿌리 보는 것처럼 순차적으로 훑는다는 것이다.

-> 배열에 가장 최적의 답이 담겨져 있다.

 

 

📌 해결 방법은 배열을 만들어서 횟수를 구하는 것과 마찬가지로 배열의 값으로 이전 노드값을 저장하는 것이다. <- 사실 이것이 BFS의 최대 장점

import sys
import collections
from collections import deque

def node(x):
    arr = []
    tmp = x
    for i in range(res[k]+1):
        arr.append(tmp)
        tmp = his[tmp]
    print(" ".join(map(str,arr[::-1])))

n,k = map(int,sys.stdin.readline().split())
MAX = 100000
res = [0]*(MAX+1) # 횟수를 저장하는 배열
his = [0]*(MAX+1) # 이전 노드의 값을 저장하는 배열
dq = deque()
dq.append(n)
anw = 0

while dq:
    ex = dq.popleft()
    if ex == k:
        print(res[ex])
        node(ex)
        break
    for num in (ex+1,ex-1,ex*2):
        if 0 <= num <= MAX and res[num] == 0:
            res[num] = res[ex] + 1
            his[num] = ex
            dq.append(num)