[ SW Expert Academy ] 5247. 연산

보자마다 dfs라고 생각했다.. 그런데 maximum recursion depth exceeded 에러가 나서 읭? 

왜 깊이 제한 에러가 나지..? 회귀하도록 조건 잘 걸어준 것 같은데...?

def dfs(current, m, depth):
    global answer
    if current > 100000 or depth >= answer:
        return
    if current == m:
        answer = min(answer, depth)
        return

    dfs(current+1, m, depth+1)
    dfs(current-1, m, depth+1)
    dfs(current*2, m, depth+1)
    dfs(current-10, m, depth+1)

if __name__ == "__main__":
    T = int(input())
    for test_case in range(1, T+1):
        answer = 1e9
        n, m = map(int, input().split())
        dfs(n, m, 0)
        print("#{} {}".format(test_case, answer))

 

if depth> answer 리턴문에서 answer대신에 작은 값을 넣어주면 답을 또 제대로 나온다.. 뭘까? 

 

 

 

다른 분들 풀이 궁금해서 검색해보니 모든 분들이 bfs로 푸셨더라.. 이게 원래 좀 bfs유형으로 유명한 문제인가봐..

 

from collections import deque


def bfs(n, m):
    queue = deque()
    queue.append((n, 0))
    check = {}
    while queue:
        item, count = queue.popleft()
        if check.get(item, 0): continue
        check[item] = 1
        if item == m: return count
        count += 1
        if 0 < item + 1 <= 1000000:
            queue.append((item + 1, count))
        if 0 < item - 1 <= 1000000:
            queue.append((item - 1, count))
        if 0 < item * 2 <= 1000000:
            queue.append((item * 2, count))
        if 0 < item - 10 <= 1000000:
            queue.append((item - 10, count))


if __name__ == "__main__":
    T = int(input())
    for test_case in range(1, T+1):
        n, m = map(int, input().split())
        print("#{} {}".format(test_case, bfs(n, m)))