[Swift] 2019 KAKAO BLIND RECRUITMENT 길 찾기 게임

Problem

 

코딩테스트 연습 - 길 찾기 게임

---

Solution

 

해당 문제는 "이진트리 " 문제입니다.

 

이진 트리는 각각의 노드가 최대 두 개의 자식 노드을 가지고 있고 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

 

1. 초기에 필요한 변수들을 세팅해줍니다.

 

//부모와 자식을 담을 이중배열
var parentsChildren:[[Int]] = Array(repeating: [], count: nodeinfo.count + 1)
//각 노드의 범위들을 담을 배열
var ranges = Array(repeating: [ClosedRange<Int>](), count: nodeinfo.count + 1)
//전위순회 담을 배열
var preorder:[Int] = []
//후위순회를 담을 배열
var postorder:[Int] = []
//가장 높은 레벨
let maxLevel:Int = nodeinfo.max{$0[1] < $1[1]}?[1] ?? 0
//레벨에 노드들의 담을 배열
var levels = Array(repeating:[Int](), count: 1000)

 

2. 레벨에 맞춰 노드들을 세팅해줍니다.

 

각 노드의 y값을 levels의 인덱스로 노드를 넣어줍니다.

 

(아래 소스코드에서 setLevelsNode 를 참고해주세요!)

 

3. 레벨과 범위에 맞춰 부모와 각 자식들을 세팅해줍니다.

 

아래와 같이 노드들의 위치를 표시했다면 이제 자식들을 세팅해야하는데요.

 

 

 

여기서 저는 5번이 누구의 자식이 되야하는지 헷갈렸는데요.

 

이렇게 9번의 자식이 될 수도 있는거 아닌가? 그러면 어떻게 자식을 정해야하 하지? 하다가

 

 

아 가장 부모 레벨의 있는 노드의 x 기준으로 가장 가까운 노드가 부모가 되는구나!

 

라고 풀었더니 34.5점이 나오더라구요....

 

그래서 카카오 풀이를 보니 이진 트리는 각 노드에 왼쪽과 오른쪽의 자식이 결정된다고 합니다..

 

예를 들면 아래와 같이 바로 아래 레벨이면서 왼쪽에 있는 4번이 왼쪽 자식이 되는 것이고 오른쪽에 있는 2번이 오른쪽 자식이 됩니다.

 

또한 4번 아래 1번은 4번과 2번 중 왼쪽에 있는 노드가 부모가 되므로 2번의 자식이 될 수 없는 것이죠!

 

 

같은 원리로 5번이 9번의 자식이 될 수 없고 8번의 자식이 됩니다.

 

 

 

자식의 왼쪽 범위는 부모의 왼쪽 범위부터 현재 자식의 x 까지 오른쪽 범위는 현재의 x부터 부모의 오른쪽 범위까지로 세팅해줍니다.

 

( 아래 소스코드에서 setParentsChilren을 참고해주세요!)

 

4. 전위 순회한 값을 저장한다.

 

위에서 자식과 부모를 세팅한 배열을 DFS 방식으로 순회하면서 차례로 방문한 노드들을 담아줍니다.

 

(아래 소스코드에서 searchPreorder를 참고해주세요!)

 

5. 후위 순회한 값을 저장한다.

 

DFS와는 정반대로 오른쪽 맨 끝 리프노드부터 차례로 왼쪽 맨 위 루트 노드까지 차례로 방문한 노드들을 담아줍니다.

 

(아래 소스코드에서 searchPostorder를 참고해주세요!)

 

6. 전위 순회한 값과 후위 순회한 값을 반환해줍니다.

---

Source Code