[programmers] 길찾기 게임

---

로직

** 이 문제는 트리문제이다  **

1. 트리를 순회하는 방법은 검색을 통해 쉽게 알 수 있으므로 문제가 되지 않습니다.
2. 이 문제의 핵심은 좌표 값으로 주어지는 노드들을 트리로 구성하는 부분입니다.
3. 트리를 만들기 위해 y값을 이용해서 각 노드의 level을 분리하고,
현재 노드의 자식노드가 가질 수 있는 x값을 이용해서 현재노드의 왼쪽, 오른쪽 자식을 정확하게 찾는 것이 중요하다
4. 각 노드의 왼쪽, 오른쪽 자식노드 찾기
- 먼저 노드 P의 x의 값을 Px, 현재노드의 자식노드가 가질 수 있는 x의 범위를 Lx, Rx(Lx < Px < Rx)
- 또 어떤 노드 K의 x값을 Kx -> 만약 현재 노드의 바로 다음 레벨에 Lx ≤ Kx < Px를 만족하는 노드 K가 있으면 -> K는 노드 P의 왼쪽 자식
- 노드 K의 자식 노드가 가질 수 있는 x값의 범위 : Lx ≤ x ≤ Px – 1 (x ≠ Kx)
- 현재 노드의 바로 다음 레벨에 Px < Kx ≤ Rx를 만족하는 노드 K -> Px + 1 ≤ x ≤ Rx (x ≠ Kx)
5. 위 과정을 재귀적으로 반복하면서 각 노드의 왼쪽, 오른쪽 자식을 찾아주면 트리를 구성할 수 있습니다.

6. 노드별 왼쪽, 오른쪽 자식을 찾는 방법
- 재귀적으로 순회하며 트리를 만들면 같은 level의 노드는 x값이 작은 노드부터 방문
- 큐를 트리의 레벨만큼 만들어 두고, x축 기준으로 오름차순 정렬된 노드들을 y축 값이 같은 노드끼리 각 큐에 넣어두면 큐의 front를 확인하는 방법으로 O(1)에 찾을 수 있
- 트리를 구성:O(N), 시간 복잡도 : O(NlogN)

 

코드

 

주의할 점

1. 우선 트리 아직은 너무 어렵다,,, 처음 트리문제를 풀어서그런지 구현하는 데 있어서 다른사람들의 코드로 이해하는걸 목표로했다.