코딩테스트 연습 - 길 찾기 게임 (2019 KAKAO BLIND, 전위순회, 중위순회, 후외순회)

# 주소

https://school.programmers.co.kr/learn/courses/30/lessons/42892#qna

프로그래머스

# 문제

전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다.
내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.

라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.

그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.

라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

아래 예시를 확인해보자.

라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)

이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다.

위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.

• 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
• 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다.

그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다.

이제 당신이 나설 때가 되었다.

곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때,
노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

제한사항

• nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
  • nodeinfo의 길이는 1 이상 10,000 이하이다.
  • nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
  • 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
  • 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
  • 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

---

입출력 예nodeinforesult

[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]

[[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

입출력 예 설명

# 문제 해설 및 코드 리뷰

import java.util.*;
class Solution {
    static class Node implements Comparable<Node>{
        int x;
        int y;
        int num;
        Node left;
        Node right;
        Node(int num, int x, int y, Node left, Node right){
            this.x = x;
            this.y = y;
            this.num = num;
            this.left = left;
            this.right = right;
        }
        @Override
        public int compareTo(Node o) {
            if(this.y == o.y)
                return this.x - o.x;
            return o.y - this.y;
        }
    }
    static int[][] answer;
    static int index;
    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        ArrayList<Node> list = new ArrayList<>();
        for(int i = 0; i < nodeinfo.length; i++)
            list.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1], null, null));
        Collections.sort(list);

        Node root = list.get(0);
        for(int i = 1; i < list.size(); i++)
            NodeInput(root, list.get(i));
        index = 0;
        preOrder(root);
        index = 0;
        postOrder(root);
//        index = 0;
//        midOrder(root);
        return answer;
    }
    static void postOrder(Node root){
        if(root != null){
            postOrder(root.left);
            postOrder(root.right);
            answer[1][index++] = root.num;
        }
    }
    static void preOrder(Node root){
        if(root != null){
            answer[0][index++] = root.num;
            preOrder(root.left);
            preOrder(root.right);
        }
    }
//    //중위 순회
//    static void midOrder(Node root){
//        if(root != null){
//            midOrder(root.left);
//            answer[0][index++] = root.num;
//            midOrder(root.right);
//        }
//    }
    static void NodeInput(Node parent, Node child){
        if(parent.x > child.x){
            if(parent.left == null)
                parent.left = child;
            else
                NodeInput(parent.left, child);
        }else{
            if(parent.right == null)
                parent.right = child;
            else
                NodeInput(parent.right, child);
        }
    }
}

트리를 잘 이해하고 있어야 풀 수 있는 문제입니다.

트리란 방향성이 없는 간선을 가지는 것이 특징이기 때문에 순환하지 않습니다.

때문에 단방향의 구조라고 이해할 수 있으며 이를 이해하기 위해선 노드의 개념에 대해서도 잘 알고 있어야 합니다.

우선 트리의 종류먼저 살펴볼텐데요.

트리에는 기본적으로 높이(depth)가 존재합니다.

이 높이란 것은 level과 같은 개념으로서 1번 노드는 1

2번과 3번노드는 2

4, 5, 6, 7은 3의 깊이를 가집니다.

또한 이 트리에서 가장 중심이 되는 1번 노드는 루트 노드라고도 불리며 편의상 root라고 부르겠습니다.

이 root는 트리에서 최고로 중심이 되기 때문에 부모 노드라고 부를 수 있으며 만약 부모 노드와 연결된 노드가 있다면 자식 노드라고도 부를 수 있습니다.

(이진 트리와 완전 이진 트리 등의 개념에 대해서도 알아보시길 추천드립니다.)

 

# 전위순회(Preorder Traversal)

제일 먼저 그림에 나와있는 트리는 전위순회입니다.

전위 순회란 부모 노드가 중심이 되어 저희가 보는 왼쪽방향부터 차례로 탐색을 진행합니다.

화살표의 방향을 잘 따라가보면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 번 노드 순으로 탐색이 진행되는 것을 알 수 있습니다.

정리하자면 부모노드 -> 자식의 왼쪽 노드 -> 오른쪽 노드 순으로 탐색이 진행됨을 알 수 있겠네요.

 

# 중위순회(Inorder Travereal)

이 부분이 많이 헷갈렸습니다.

화살표의 방향을 먼저 살펴보면 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7 순으로 탐색이 진행됩니다.

간단하게 생각하자면 중위순회는 왼쪽에서 오른쪽 진행된다. 이렇게도 생각할 수 있겠습니다.

 

# 후위순회

화살표는 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1 노드 순서로 방문합니다.

왼쪽 노드 -> 오른쪽 노드 -> 부모노드 순으로 탐색을 진행하게 된답니다.

코드로 살펴보겠습니다.

answer = new int[2][nodeinfo.length];
ArrayList<Node> list = new ArrayList<>();
for(int i = 0; i < nodeinfo.length; i++)
    list.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1], null, null));
Collections.sort(list);

정답이 될 answer배열을 2 x nodeinfo의 크기만큼 생성합니다.

Node클래스 타입의 list를 하나 만들건데요.

보통 간선을 표현할 때에는 ArrayList를 이용하여 Node 클래스를 오버라이딩하여 사용을 많이 하곤 합니다.

양방향 간선을 나타내고 싶을 때에는 arr[0][1] = 1, arr[1][0] = 1과 같이 나타낼 수도 있으며

단방향 간선을 나태내고 싶을 때에는 0에서 1로 가는 간선일 경우 arr[0][1] = 1로도 나타낼 수 있겠습니다.

이것은 비용이 1이 드는 그래프를 예시로 든 것입니다만 비용이 각각 간선마다 다를 경우 arr[0][2] = 3, arr[2][4] = 1일 경우 0에서 4로 가는 비용이 4가 드는 형식으로, 다익스트라를 이용하여 구할 수도 있겠습니다.

그래프를 공부하면서 트리도 같이 알아두면 좋은 것 같습니다. 제가 트리는 많이 안풀어봐서 배울 부분이 많은 문제였습니다.

다시 본론으로 돌아가

for(int i = 0; i < nodeinfo.length; i++)
    list.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1], null, null));
Collections.sort(list);

list에 값을 add하는데 i + 1번 노드에 x값과 y값을 각각 넣고 left와 right에는 아직 값이 없으므로 null을 주입합니다.

여기에서 nodeinfo[i][0]값은 x좌표, nodeinfo[i][1]값은 y좌표를 뜻하는데 y좌표는 값이 level 마다 일정하단 것도 기억하시면 좋겠습니다.

자 문제에서 이렇게 주어졌다면 저희는 이걸 어떻게 트리로 나타낼 수 있을까요?

이를 위해 list를 정렬을 할 필요가 있습니다.

어떻게?

y를 내림차순으로 정렬한 뒤 x는 오름차순으로 정렬하는 것입니다.

그렇다면 y값이 제일 큰 노드가 루트 노드(부모 노드)가 될 것이고 이후에 자식 노드를 꾸릴 수 있게되니까요.

여기서 x좌표가 되는 값들을 오름차순으로 정렬하는 이유는 트리를 나타낼 때 왼쪽에 있는 것 부터 값을 넣기 위함입니다.

이 그림사진을 잘 보시기 바랍니다.

또한 정렬을 위한 Comparable 인터페이스를 상속받아 구현하였는데 같이 보겠습니다.

static class Node implements Comparable<Node>{
    int x;
    int y;
    int num;
    Node left;
    Node right;
    Node(int num, int x, int y, Node left, Node right){
        this.x = x;
        this.y = y;
        this.num = num;
        this.left = left;
        this.right = right;
    }
    @Override
    public int compareTo(Node o) {
        if(this.y == o.y)
            return this.x - o.x;
        return o.y - this.y;
    }
}

모든 파라미터를 오버라이딩하게끔 구현하였습니다.

그리고 정렬을 위해 y값을 내림차순으로 정렬하고 만약 y값이 같을 때에는 x값을 오름차순으로 정렬하였습니다.

Node root = list.get(0);
for(int i = 1; i < list.size(); i++)
    NodeInput(root, list.get(i));

여기까지 했으면 순조롭습니다.

당연히 정렬된 트리 중 첫 번째 인덱스를 뽑아온 것은 루트노드가 됩니다.

그리고 루트노드와 list에서 뽑아올 다음 노드들과의 트리 구성을 위해 함수를 만들었습니다.

static void NodeInput(Node parent, Node child){
    if(parent.x > child.x){
        if(parent.left == null)
            parent.left = child;
        else
            NodeInput(parent.left, child);
    }else{
        if(parent.right == null)
            parent.right = child;
        else
            NodeInput(parent.right, child);
    }
}

여기서 잘 보시기 바랍니다.

parent노드와 child노드의 x좌표를 먼저 비교할 것입니다.

비교하여 부모노드의 x보다 작으면 왼쪽으로, 크면 오른쪽에 노드를 설치할텐데요.

그 속에서도 left에 자리가 빈다면 child가 left자리로 들어가게 되고 자리가 있다면 해당 left자리와 child의 x좌표가 해당 자리를 두고 서로 대소관계를 비교하며 싸워야겠지요.

이렇듯 재귀함수로 계속하여 list에 있는 모든 x값들을 root노드와 비교하여 재귀 재귀 재귀를 거듭하시면 되겠습니다.

다행히 배열 값이 그리 크지 않기 때문에 시간복잡도 측면에선 문제 없을 것이라 생각듭니다.

(실제로 O(log N)만큼 듭니다.)

index = 0;
preOrder(root);
index = 0;
postOrder(root);

static void postOrder(Node root){
    if(root != null){
        postOrder(root.left);
        postOrder(root.right);
        answer[1][index++] = root.num;
    }
}
static void preOrder(Node root){
    if(root != null){
        answer[0][index++] = root.num;
        preOrder(root.left);
        preOrder(root.right);
    }
}

이제 전위순회와 후위순회를 차례로 시행하면 되겠습니다.

preOrder라 적힌 전위순회를 먼저 살펴보면 answer값에 root.num을 먼저 넣을건데요.

아까도 살펴봤듯이 전위순회는 부모노드가 중심이 되어 부모 -> 자식왼쪽 -> 자식 오른쪽 순으로 탐색합니다.

따라서 root의 num을 최초에 삽입 후 재귀함수를 시행할텐데요.

왼쪽 노드 탐색 -> 오른쪽 노드 탐색이므로 먼저 preOrder함수를 시행합니다.

 

후위순회의 경우 왼쪽 노드 -> 오른쪽 노드 -> 부모 노드이기 때문에 함수를 두 번 시행한 뒤 answer에 값을 넣어주도록 하겠습니다.

 

그렇다면 중위순회는 어떻게 생겼을까요?

    static void inOrder(Node root){
        if(root != null){
            inOrder(root.left);
            answer[0][index++] = root.num;
            inOrder(root.right);
        }
    }

중위순회의 경우 왼쪽 노드 -> 부모노드 -> 오른쪽 노드이기 때문에 inOrder함수  사이에 answer값에 num을 넣었습니다.

만약

위의 그림에서 중위순회를 출력한다면

6 -> 9 -> 4 -> 1 -> 5 -> 8 -> 7 -> 2 -> 3이 출력될 것입니다.

전위순회와 중위순회가 조금 헷갈릴 수 있는데 전위는 부모 -> 왼 -> 오

중위는 왼 -> 부모  -> 오

후위는 왼 -> 오 -> 부모 순인거 머릿속으로 상상하시면서 구현하시면 금방 하실 수 있습니다.

감사합니다.