23.03.06 파이썬 코딩 퀴즈#183 길 찾기 게임(프로그래머스 스쿨)

이번 문제는 길 찾기 게임 이다.

길 찾기 게임의 규칙은 아래와 같다.

1. 트리를 구성하는 모든 노드의 x,y 좌표 값은 정수로 전달된다.

2. 모든 노드는 서로 다른 x 값을 가진다

3. 같은 레벨에 있는 노드는 같은 y 값을 가진다.

4. 자식 노드의 y 값은 항상 부모 노드보다 작다.

5 한 부모노드를 기준으로 왼쪽트리와 오른쪽 트리의 x 값의 크기는 왼쪽트리 <= 부모노드 <=오른쪽 노트 이다.

전달받은 각 노드들을 간선으로 모두 이으면 위와 같은 모양이 나오며, 이를 전위 순회, 후위 순회를 하게 되면 모든 노드를 방문하는 각 값을 얻을 수 있다.

각 노드의 번호는 nodeinfo의 index+1 번이며, [x,y] 순서이다.

이제 전달받은 nodeinfo 를 순회하는 [전위순회, 후위순회] 배열을 return 하면 된다.

 

먼저 전위순회 와 후위순회의 개념부터 정리하고 넘어가자

전위순회랑 가장 최상위 부모 노드에서 시작하여, 좌측트리를 타고 진행한다. 분기점에서도 마찬가지로 좌측을 우선 탐색하게 된다.

즉 최상위 부모 노드를 기준으로 7->4 먼저 탐색하게 되고, 그 다음 6번과 1번중 좌측에 있는 6번을 탐색한다.

9번을 탐색한 다음에는 다시 부모 노드로 돌아가 아직 탐색하지 않은 4번으로 이동한다. 그리고 4번 노드 기준 우측트리를 완전히 다 탐색하고 나서야 7번 노드로 올라가 우측 트리를 탐색한다.

 

후위순위의 시작점은 해당 트리의 가장 좌측 최하위 자식 노드에서 시작한다.

만약 부모노드가 우측 트리를 가지고 있는 경우라면, 부모노드를 방문하지 않고, 그 우측 트리의 최하위 자식 노드로 이동한다. 그리고 다시 부모노드까지 올라오면서 다른 트리가 존재하지 않는다면 그 부모노드를 방문하고 상위로 올라간다.

즉, 시작은 9번 노드에서 시작하고 바로 6번 노드를 방문한다. 이때 4번 노드는 우측 트리를 가지고 있으므로, 우측 트리의 좌측 트리의 최하위 자식노드 (위 예시에서는 우측트리는 일직선 배치이기 때문에 제일 하위인 5번 노드로 이동한다.)인 5번 노드를 방문한다. 그리고 트리를 타고 올라오다가 해당 트리의 최상위 부모인 4번 노드를 방문한뒤, 다시 7번 노드의 우측 트리로 이동하여 3번->2번->7번 노드를 방문하고 종료된다.

트리를 구성할때 노드의 y 값에 의해 level 이 결정되며, x 값에 의해 좌/우 트리 위치가 결정된다.

그리고 위 그림과 같이 부모 노드들의 x 값에도 영향을 받는다, 즉 8번 노드의 경우 7번 노드보다 x 값이 작기 때문에 절대 2번 노드의 좌측 트리가 될 수 없다. 마찬가지로 5번 노드의 경우 1번 노드보다 x값이 크기 때문에 1번 노드의 우측노트로 존재 가능하고, 이미 상위 level(부모)의 8번 노드가 존재하기에 8번의 자식 노드로 존재하게 된다.

먼저 코드를 작성하기 전에, 이진 트리를 구성할 노드를 생서할 class를 선언해 주었다.

특별한건 없고, 위에서 부터 순서대로 노드의 정보 / 좌측트리/우측트리/부모노드/ 노드번호 순서로 전달 된다.

그리고 노드를 탐색할 두개의 함수를 새로 선언해 주었다.

preOrder()는 전위순회, postOrder() 는 후위순회를 담당한다.

각 함수들은 현재 root(탐색할 위치) 와 빈 배열 arr을 전달받아 작동하며, 해당 root를 기준으로 좌/우 트리를 탐색한다.

한가지 다른 점은 전위순회의 경우 방문한 노드를 먼저 배열에 담고, 후위순회의 경우 모든 노드를 방문한 뒤 마지막으로 root를 배열에 담아 반환한다는 점이다.

이제 본격적으로 전달받은 nodeinfo 를 이용하여, 각 노드들을 생성하고 탐색을 시작해보자.

먼저 전달받은 nodeinfo 를 반복문을 통해 돌면서, 해당 노드의 번호를 각 nodeinfo 의 요소의 마지막에 추가로 전달해주었다. [x, y, 노드번호] 로 저장된다.

그리고 x[1] 즉 y값을 기준으로 내림차순 정렬해주면, 가장 최상위 노드들부터 정렬이 된다.

이제 다시 반복문을 통해 노드들을 작성해 주어야 한다.

첫번째 만나는 if문은 nodeinfo[0]번만 해당된다. 즉 최상위 부모 노드로 nodeinfo[0] 이 선언된다.

그리고 자식 노드들의 경우는 else문을 돌게 되는데 먼저 curTree 는 부모 노드가 된다.

그리고 자식 노드의 x값과 부모 노드의 x 값을 비교하고, 비교 결과로 인해 우측/좌측 노드가 결정되며, 만약 해당 노드의 우측/좌측 노드가 이미 존재하는 경우라면, curTree를 curTree의 좌측/우측 노드로 변환한뒤 다시 값을 확인하게 된다.

 

이를 다시 예제를 통해 확인해 보면,

위에서 전달받은 nodeinfo 를 x[1]기준으로 오름차순 정렬하면, 

[[8, 6, 7], [11, 5, 2], [3, 5, 4], [5, 3, 1], [13, 3, 3], [1, 3, 6], [7, 2, 8], [2, 2, 9], [6, 1, 5]] 가 된다.

index 0 은 최상위 부모로 결정되며, 1, 2 는 x값 11과 5에 따라 우측 / 좌측 노드로 결정된다.

그리고 다시 index3을 살펴보면, root는 항상 [8,6,7] 이고, 해당 root랑 비교를 하게 되며, x값을 비교하여 우측노드로 선언되어야 한다. 하지만 이미 index1 이 우측 노드로 선언 되었기에, else문에 의해 현재 root.right 가 currTree가 되며, 다시 index1과 index3을 비교하게 된다. 그리고 index3 의 x값이 더 크므로, index1(2번 노드)의 우측노드로 선언이 된다.

그리고 일련의 과정들을 모두 거치게 되면 비로서 nodeinfo를 활용한 이분트리가 완성이 되는 것이다.

 

간혹 비슷한 코드를 작성하고도 런타임 오류에 걸리는 경우가 있는데, 이는 파이선 자체적으로 재귀횟수에 제한을 걸어 두어서 그렇다.

이 경우에는 위 코드를 추가로 작성해주면, 함수의 재귀횟수제한을 증가시켜서 문제를 해결 가능하다.