[프로그래머스] 길 찾기 게임(09.01)

문제

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

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

 

접근법

문제 그대로 그래프를 구현해서 풀었다.

그래프 클래스를 만들어서 삽입하는 로직을 만들어주는것이 포인트였다.

우선 y좌표 값이 높고 x좌표 값이 낮은 순으로 정렬했다.

그렇게 되면 그래프에 삽입이 되는 순서가 완성이 된다.

그 후 root 객체를 전역변수로 빼고 root를 타고 내려가면서 알맞은 위치에 삽입했다.

 

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public Node root;

    public class Node{
        private Pair data;
        private Node left;
        private Node right;

        public Node(Pair data){
            this.data = data;
            this.left = null;
            this.right = null;
        }

        public void add(Pair data){
            Node node = new Node(data);
            if(root == null){
                root = node;
                return;
            }
            Node current = root;
            while(true){
                Node parent = current;
                if(data.x < current.data.x){
                    current = current.left;
                    if(current == null){
                        parent.left = node;
                        return;
                    }
                }else{
                    current = current.right;
                    if(current == null){
                        parent.right = node;
                        return;
                    }
                }
            }
        }
    }
    
    public class Pair implements Comparable<Pair>{
        int x;
        int y;
        int num;

        public Pair(int x, int y, int num) {
            this.x = x;
            this.y = y;
            this.num = num;
        }

        @Override
        public int compareTo(Pair o) {
            if(this.y < o.y)
                return 1;
            else if(this.y > o.y)
                return -1;
            else{
                if(this.x < o.x)
                    return -1;
                else if(this.x > o.x)
                    return 1;
                return 0;
            }
        }
    }
    
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][nodeinfo.length];

        List<Pair> list = new ArrayList<>();

        for(int i=0;i<nodeinfo.length;i++){
            list.add(new Pair(nodeinfo[i][0], nodeinfo[i][1], i+1));
        }

        Collections.sort(list);

        for(int i=0; i<list.size();i++){
            if(i==0){
                root = new Node(list.get(i));
                continue;
            }
            root.add(list.get(i));
        }

        List<Integer> preOrderList = new ArrayList<>();
        List<Integer> postOrderList = new ArrayList<>();
        preOrder(root, preOrderList);
        postOrder(root, postOrderList);

        for(int i=0;i<nodeinfo.length;i++){
            answer[0][i] = preOrderList.get(i);
            answer[1][i] = postOrderList.get(i);
        }

        return answer;
    }

    private void preOrder(Node node, List<Integer> list){
        if(node == null)
            return;
        list.add(node.data.num);
        preOrder(node.left, list);
        preOrder(node.right, list);
    }


    private void postOrder(Node node, List<Integer> list){
        if(node == null)
            return;
        postOrder(node.left, list);
        postOrder(node.right, list);
        list.add(node.data.num);
    }
}