런타임에러
숨바꼭질, 숨바꼭질2, 숨바꼭질3에 이어 연계되는 문제입니다. 문제에 대한 자세한 설명은 없으니 미리 풀어 보시는 것을 권장합니다!!
사실 어렵지 않은 BFS 문제인데 왜 런타임 에러가 뜨는지 이해를 못하다가 1월 7일 BOJ에서 런타임 에러 업데이트로 이유를 보여주기 시작했습니다.. RecursionError.. 재귀 함수가 limit에 부딪혀 발생하는 문제였죠. 이 이유임을 확인하고 바로 통과했습니다.
분명 로직상 문제는 없었거든요.
sys.getrecursionlimit()재귀는 최대 10만 번 돌아갈 테니까 기본 limit을 확인해봤더니 아니 세상에 1000이더라고요?
이렇게 낮은 줄은 생각도 못했습니다 ㅠㅠ
sys.setrecursionlimit(10**5)그냥 넉넉하게 풀어줬습니다..
해결방법
하단의 소스코드가 상당히 해괴망측합니다.. 에러에 부딪히다 보니 이 예외 저 예외 이것저것 추가하다 보니 이렇게 되었네요.
숨바꼭질 문제들을 스스로 푸셨다면 사실 막힐 이유도 없는 문제이고 심지어 스페셜 저지로 정답이 여러 개인 문제입니다.
문제를 풀다 보니 Union Find가 생각나더라고요. 배열을 하나 만들고 다음 방문지에 이전 방문지를 기록하는 형태로 만들어 뒀습니다.
5 17 입력 시 5 4 8 16 17이 나오는 과정을 살펴볼게요.
| ARRAY | index | 4 | 5 | 8 | 16 | 17 |
| value | 5 | 5 | 4 | 8 | 16 |
그 사이 인덱스는 생략하고 정답 인덱스만 살펴보면 값은 위와 같습니다. 그래서 재귀 함수로 17을 가리키면 16을 가리키고 16으로 가면 8, 8로 가면 4, 4 로가면 5 이걸 역순으로 출력하는 거죠!!
그래서 해당 순서를 answer이라는 deque에 담아 마지막에 출력하는 방식을 선택했습니다.
소스 코드
##########################################################
import sys
from collections import deque
direction = [[0,1],[-1,0],[1,0],[0,-1]] #for BFS
input = sys.stdin.readline
def ip():return input().rstrip()
def lip():return list(ip())
def ips():return ip().split()
def ii():return int(input())
def mii():return map(int,ips())
def lmii():return list(mii())
##########################################################
sys.setrecursionlimit(10**5)
maxnum = 100001
n,k = mii()
if n>k:
print(n-k)
for i in range(n,k-1,-1):
print(i,end=' ')
sys.exit()
elif n==k:
print(0)
print(n)
sys.exit()
arr = [-1]*maxnum
tree = dict()
def solve():
q=deque([n])
arr[n]=0#초기화
# tree[n] = n
while q:
x = q.popleft()
if x==k:
return
for i in [x+1,x-1,x*2]:
if 0<=i<maxnum:
if arr[i]==-1 :#첫방문
tree[i]=x
arr[i] = arr[x]+1
q.append(i)
solve()
print(arr[k])
answer= deque()
def search(num):
global answer
answer.append(num)
if num==n:return
tt = tree[num]
search(tt)
search(k)
for z in range(len(answer)-1,-1,-1):
print(answer[z],end=' ')
