[백준/1634] 완전 이진트리 (Python)

Problem : https://www.acmicpc.net/problem/1634

1634번: 완전 이진트리

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:14:26

 

---

 

문제 설명

 

 

‘k-레벨 완전 이진 트리’는 모든 노드의 분지수(차수)가 0이거나 혹은 2이고, 레벨 1에 있는 노드 수가 2^0, 레벨 2에 있는 노드수가 2^1, ... , 레벨 k에 있는 노드 수가 2^(k-1)이며, 총 노드 수는 2^k-1인 이진 트리를 말한다. 두 개의 k-레벨 완전 이진 트리 T1과 T2가 있고, 각 트리의 단말 노드들, 즉 레벨 k의 노드들에 대하여 L={1,2,...,N}에 속하는 서로 다른 정수들이 할당되어 있다. 다음 조건을 만족하는 L의 부분 집합 s를 찾는 프로그램을 작성하시오.

 

• S에 속하는 모든 쌍의 정수 x, y에 대하여 T1과 T2에서 x가 할당된 노드와 y가 할당된 노드 사이의 거리가 서로 같다. 두 노드 사이의 거리는 두 노드를 잇는 경로가 지나는 에지의 수이다.
• S에 속한 원소의 수는 반드시 최대이어야 한다.

왼쪽 그림이 T1, 오른쪽 그림이 T2이다.

예를 들어, k = 4인 경우에 아래 그림과 같이 단말 노드에 정수가 할당된 두 트리 T1과 T2가 주어져 있다고 하자. 두 트리 T1과 T2의 단말 노드들에 할당된 수들을 왼쪽에서 오른쪽으로 차례대로 쓴 것이 각각 (4, 2, 1, 3, 6, 7, 5, 8)과 (2, 7, 4, 8, 3, 1, 6, 5)라고 하자. 이 경우에 구하고자 하는 답은 S = {1, 3, 7, 8}이다. 예를 들어, S에 속하는 한 쌍의 정수 3, 7에 대하여 T1과 T2에서 3이 할당된 노드와 7이 할당된 노드 사이의 거리가 6으로 서로 같다.

 

 

 

입력 및 출력

 

입력

 

첫줄에 두 트리 T1과 T2의 레벨 k (1<=k<=12)가 주어진다. 둘째 줄에 T1의 단말 노드들에 할당된 수들이 왼쪽에서 오른쪽으로 차례로 주어진다. 셋째 줄에 T2의 단말 노드들에 할당된 수들이 왼쪽에서 오른쪽으로 차례로 주어진다.

 

출력

 

첫 줄에 주어진 조건을 만족하는 최대 집합 에 속하는 원소의 수를 출력한다.

 

입력 예시

 

4
4 2 1 3 6 7 5 8
2 7 4 8 3 1 6 5

 

출력 예시

 

4

 

 

---

 

풀이

 

언뜻 보면 모든 거리를 전부 구해야하나..싶을 수 있겠다. 하지만 잘 생각해보면 더 쉬운 풀이가 존재한다. 트리 T1을 기준으로, 트리 T2를 동형을 유지하며 임의로 재배열한다고 가정하자.  트리의 어느 지점의 노드를 기준으로, 왼쪽 자식 트리와 오른쪽 자식 트리의 위치를 바꾼다고 해 보자. 하지만 트리는 동형이다. 트리의 각 노드의 깊이, 부모 노드 및 자식 노드에 대한 정보 등은 동일하다.

 

여기서 우리는 동형인 트리는 두 노드 사이의 거리 정보 역시 유지함을 알 수 있다. 따라서 T2를 마음껏 동형을 유지하며 변형(즉 각 서브트리에 대해 자식 순서를 바꾸어 봄)하였을 때, T1과 최대로 일치하는 경우를 찾으면 된다. 그리고 그 때의 일치하는 단말 노드의 수가 정답이 된다.

 

p.s. 여기서 총 시간복잡도는 O(NlogN) 이상이 될 것 같은데... 2 번 호출되니까 좀 더 커야할 것 같기도 하고... Master's theorem을 다시 뒤적여 봐야할 듯 싶다.

 

풀이 코드

k = int(input())
T1 = list(map(int, input().split()))
T2 = list(map(int, input().split()))

def div_and_con(depth, start, end, left, right) :
  if depth == k :
    return 1 if T1[left] == T2[start] else 0

  mid = (start + end) // 2
  center = (left + right) // 2
  orig_result = div_and_con(depth+1, start, mid, left, center) + div_and_con(depth+1, mid+1, end, center+1, right)
  rev_result = div_and_con(depth+1, mid+1, end, left, center) + div_and_con(depth+1, start, mid, center+1, right)

  return max(orig_result, rev_result)

print(div_and_con(1, 0, 2**(k-1)-1, 0, 2**(k-1)-1))

풀이 완료!