무한 이진 트리 (백준 2078번)

무한 이진 트리

2078번: 무한이진트리

2078번: 무한이진트리

 

처음 이 문제를 풀었을 때 테스트 코드는 맞는데, 메모리 초과가 계속 발생해서 고민했던 문제다.

 

DFS를 사용해볼까 고민 했었는데, DFS를 쓰면 밑을 찍고 올라와야 하는데, 바텀업 방식으로 (1,1 로부터 만들기 시작.) 만들다보니 바닥을 찍고 다시 돌아올 수 없을 것 같았다.

 

그래서 BFS를 사용해서 루트값으로부터 타겟 값이 나올 때 까지 이진 트리를 계속해서 만들었다.

 

메모리 초과 코드

# 무한 이진 트리
import sys
from collections import deque

a, b = map(int, sys.stdin.readline().split())
q = deque()
l, r = 0, 0
def bfs(x, y):

    q.append((x, y, 0, 0))

    while True:
        x, y, l, r = q.popleft()

        if x == a and y == b:
            return (l, r)
        
        # 오른쪽
        if x <= a and x+y <= b:
            q.append((x, x+y, l, r + 1))

        # 왼쪽
        if x+y <= a and y <= b:
            q.append((x+y, y, l + 1, r))
        
a, b = bfs(1, 1)
print(f"{a} {b}")

 

오른쪽 정점, 왼쪽 정점을 만들고 큐에 넣고 왼쪽 서브 트리면 l값을 증가, 오른쪽 서브 트리라면 r을 증가시켜 타겟을 만나면 그 l,r값을 반환하도록 했다.

 

이렇게 풀고나니 테스트 케이스는 통과하는데, 계속 메모리 초과가 발생했다…

 

때문에 다른 방식을 찾아야했다.

 

이진트리 특성상 서브 트리가 만들어지는 방법을 알면 부모의 값을 알 수 있다.

 

부모의 자식은 둘 밖에 존재할 수 없음으로, 직접 트리를 만들지 않고 타겟값으로부터 루트 정점을 만날 때까지 거꾸로 접근하면 풀 수 있었던 문제다.

 

답안 코드

# 무한 이진 트리
import sys
from collections import deque

a, b = map(int, sys.stdin.readline().split())
l, r = 0, 0
# 1, 1 부모 정점을 만나면 종료
while not (a == 1 and b == 1):
    if a > b:
        a -= b
        l += 1
    else:
        b -= a
        r += 1

print(l, r)

만약 부모의 값이 (3, 1)일때, 왼쪽자식의 경우 (4, 1), 오른쪽 자식은 (3, 4)이다.

왼쪽 자식 (4, 1)에서 (4-1, 1) 즉, (a-b, b)를 하면 부모 정점이고 오른쪽 자식에서 (a, b-a)을 해주면 부모 값을 찾을 수 있다.

 

따라서 타겟을로부터 부모를 찾아찾아 가다가 루트를 찍으면 그때의 좌, 우로 움직인 횟수를 출력해주면 되는 문제다.