[Programmers] Level 3 : 길 찾기 게임

문제 링크

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

프로그래머스

---

💡 풀이

주어진 데이터를 토대로 이진 트리를 만들고, 전위 순회, 후위 순회를 구현하면 되는 자료구조 문제입니다. 

데이터 처리

우선, 각 노드를 저장할 클래스를 만들어 줍니다. 

Node

class Node {
    int index;
    int x, y;
    Node left, right;

    Node(int index, int x, int y) {
        this.index = index;
        this.x = x;
        this.y = y;
        left = null;
        right = null;
    }
}

 

좌표로 주어지는 노드를 순서에 알맞게 처리하기 위해 우선순위 큐를 사용했습니다. 우선순위 큐의 정렬 조건은 다음과 같습니다. 

Y 좌표의 값이 큰 순서대로 정렬. 만약 Y 좌표 값이 같다면, X 좌표 값이 작은 순서대로 정렬

우선순위 큐

PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
    if(o1.y == o2.y) {
        return o1.x - o2.x;
    }
    return o2.y - o1.y;
});

 

이진트리 만들기

데이터를 삽입한 우선순위 큐를 토대로 `insertNode` 메서드를 만들어, 이진트리를 만들어 줍니다.

root = pq.poll();
while(!pq.isEmpty()) {
    insertNode(root, pq.poll());
}

...

void insertNode(Node parent, Node child) {
    if(child.x < parent.x) {
        if(parent.left == null) {
            parent.left = child;   
        } else {
            insertNode(parent.left, child);
        }
    } else {
        if(parent.right == null) {
            parent.right = child;
        } else {
            insertNode(parent.right, child);
        }
    } 
}

트리 탐색

만들어진 이진 트리를 토대로, 전위 순회와 후위 순회를 구현해주면 문제가 해결됩니다. 

전위순회

void preOrder(Node cur) {
    if(cur != null) {
        answer[0][index++] = cur.index;
        preOrder(cur.left);
        preOrder(cur.right);
    }
}

후위순회

void postOrder(Node cur) {
    if(cur != null) {
        postOrder(cur.left);
        postOrder(cur.right);
        answer[1][index++] = cur.index;
    }
}

전체 코드

전체적인 코드는 아래와 같습니다.

import java.util.*;

class Solution {
    PriorityQueue<Node> pq;
    Node root;
    int[][] answer;
    int index;
    
    public int[][] solution(int[][] nodeinfo) {

        answer = new int[2][nodeinfo.length];
        pq = new PriorityQueue<>((o1, o2) -> {
            if(o1.y == o2.y) {
                return o1.x - o2.x;
            }
            return o2.y - o1.y;
        });
        
        for(int i = 0; i < nodeinfo.length; i++) {
            Node node = new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]);
            pq.offer(node);
        }
        root = pq.poll();
        
        while(!pq.isEmpty()) {
            insertNode(root, pq.poll());
        }
        
        index = 0;
        preOrder(root);
        index = 0;
        postOrder(root);
        
        return answer;
    }
    
    void insertNode(Node parent, Node child) {
        if(child.x < parent.x) {
            if(parent.left == null) {
                parent.left = child;   
            } else {
                insertNode(parent.left, child);
            }
        } else {
            if(parent.right == null) {
                parent.right = child;
            } else {
                insertNode(parent.right, child);
            }
        } 
    }
    
    void preOrder(Node cur) {
        if(cur != null) {
            answer[0][index++] = cur.index;
            preOrder(cur.left);
            preOrder(cur.right);
        }
    }
    
    void postOrder(Node cur) {
        if(cur != null) {
            postOrder(cur.left);
            postOrder(cur.right);
            answer[1][index++] = cur.index;
        }
    }
    
    class Node {
        int index;
        int x, y;
        Node left, right;
        
        Node(int index, int x, int y) {
            this.index = index;
            this.x = x;
            this.y = y;
            left = null;
            right = null;
        }
    }
}