[백준] 21320. 순간이동 여행

https://www.acmicpc.net/problem/21320

문제요약

• 이진포화트리가 주어짐(최대 높이 3000)
• 특정 노드에서 시작해서 전체 노드를 탐색함
• 중복 방문이 안되기때문에 "순간이동"으로 원하는 노드로 이동
• 높이, 시작 위치가 주어질때 순간이동의 최소값 구하기

접근법

• 어려웠음, 해결하고 나서도 명확한 증명은 못하겠음.
• 몇 가지 관찰은 해보았음
  • 시작점은 트리의 왼쪽 바깥임
  • 만일 시작점이 내부였어도 왼쪽 바깥에서 시작한것과 같은 효과일 것임
  • (n, k)로 값이 정해지는 특성이 있음
  • 이동을 하면 자연스럽게 단절 되는 구간이 생길 것임(부모로 가거나, 자식으로 가거나 선택하면 다른 곳은 가지 못하므로)
  • f(n) : 높이가 n인 포화 이진트리의 최소 순간이동여행값이 존재할 것임 = 나눠지는 그룹의 최소 개수
  • 트리가 몇 개의 덩어리로 나누어지는지를 파악하면 될 것 같음
• 시작 점에서 방향을 결정해서 이동하는 방법 => 해결해지 못한 접근법
  • 처음에 아래 또는 위를 결정해서 이동할 것임
  • 아래 끝까지 가야하나, 위 끝까지 가야하나(=루트), 루트를 넘어서 반대쪽 까지 가야하나 생각하기 어려웠음
  • 시작노드를 부모로하는 하위 트리를 적절히 이동하고, 나머지를 처리하는 방식도 고민해봤으나 최적해는 아니어서 어려웠음
• 리프노드의 관찰 => 해결한 접근법
  • 어찌되었든 리프노드들도 탐색을 해야할 것임
  • 리프노드를 0, 1, 2, .... 로 번호를 부여했다고 보면
  • 0번 리프와 1번 리프를 한번에 이동하려면 0과 1의 부모를 거쳐서 이동해야함
  • 0번리프가 1번리프를 거치지 않은 상태에서 최적의 이동을 했다고 쳐도 결국은 1번리프로 순간이동을 해야함
  • 0번과 1번을 하나로 묶어서 이동을 해도 손해보지 않겠다는 접근....
  • 이런식으로 반복적으로 그룹을 만들어 나갈 수 있을 것 같음
• 리프노드들의 제거
  • 높이가 N인 경우 리프노드는 ${2^{N-1}}$개이고, 리프노드의 부모 노드는 ${2^{N-2}}$개임
  • 높이가 N인 트리에서 "리프노드 -> 리프노드 부모 -> 리프노드 + 1"를 하나의 이동단위로 본다면
  • f(N) = f(N - 2) + ${2^{N-2}}$
• 시작점에 따른 변화
  • 시작점이 "이동단위"의 부모인지 자식인지에 따라 값이 달라짐
    • 자식일 경우 : 자식 -> 부모 -> 다른 자식으로 이동 가능하기 때문에 f(N) 값을 사용할 수 있음
    • 부모일 경우 : 부모 -> 자식, 자식 으로 최초 한번은 구분이 되고 나머지는 앞서 사용했던 패턴으로 이동 가능
    • 부모일 경우 (부모 -> 자식, 자식) 패턴 말고 다른 방식으로 이동하면 값이 최적화 되지 않는 것 같음
• 구현
  • f(n) 값을 구해나감
  • n, k를 입력받았을때 k가 (f(n)을 구할때 사용한 그룹들에서) 부모일지 자식일지 판단해봄
  • k = n일 경우에는 리프노드이므로 자식노드임
  • 5이하의 숫자에 대해서 하나씩 해보면 n과 k가 홀/짝인지로 판단이 가능해짐