길 찾기 게임

문제 링크

문제 풀이 시간 : 1시간

문제 풀이 :

프로그래머스AI 추천문제를 계속 풀던 중에 정답률이 꽤 낮아보여서 풀게되었는데

문제를 처음 읽었을 때 생각보다 어려운 문제구나 싶었다.

근데 문제를 자세히 읽어보니

그냥 노드 클래스를 만들어서 트리를 만들어주면 되는 간단한 문제였다.

Node 클래스

java

class Node{
    private Integer num, x, y;
    private Node left;
    private Node right;
    
    public Node(int num, int x, int y){
        this.x = x;
        this.y = y;
        this.num = num;
    }
    
    public void setLeft(Node left){
        this.left = left;
    }
    
    public void setRight(Node right){
        this.right = right;
    }
    
    public Integer getX(){
        return x;
    }
    
    public Integer getY(){
        return y;
    }
    
    public Integer getNum(){
        return num;
    }
    
    public Node getRight(){
        return right;
    }
    
    public Node getLeft(){
        return left;
    }
}

노드 객체 생성 후 정렬

java

Node[] nodes = new Node[nodeinfo.length];
        
for(int i=0;i<nodeinfo.length;i++){//각 노드의 정보를 객체로 변환
	nodes[i] = new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]);
}
        
Arrays.sort(nodes,new Comparator<Node>(){//노드를 y내림차순, x오름차순으로 정렬
	@Override
	public int compare(Node a, Node b){
		if(a.getY()==b.getY()){
			return Integer.compare(a.getX(),b.getX());
		}
		return Integer.compare(b.getY(),a.getY());
	}
});

트리 구성

java

Node head = nodes[0]; //루트 노드

for(int i=1;i<nodes.length;i++){
    head = nodes[0];
    while(true){
        if(head.getX()<nodes[i].getX()){ //루트 노드의 x값이 현재 노드의 x값보다 작다면
            if(head.getRight() == null){ //오른쪽 자식이 없다면 오른쪽자식으로 연결
                head.setRight(nodes[i]);
                break;
            }
            head = head.getRight(); //있다면 루트 이동
        }
        else{
            if(head.getLeft() == null){
                head.setLeft(nodes[i]);
                break;
            }
            head = head.getLeft();
        }
    }
}

전,후위 순회

java

public void pre(Node now) {
    if (now == null)
        return;
        
    preorder.add(now.getNum());
    pre(now.getLeft());
    pre(now.getRight());
}
    
public void post(Node now) {
    if (now == null)
        return;
        
    post(now.getLeft());
    post(now.getRight());
    postorder.add(now.getNum());
}

전체 코드

java

import java.util.*;

class Node{
    private Integer num, x, y;
    private Node left;
    private Node right;
    
    public Node(int num, int x, int y){
        this.x = x;
        this.y = y;
        this.num = num;
    }
    
    public void setLeft(Node left){
        this.left = left;
    }
    
    public void setRight(Node right){
        this.right = right;
    }
    
    public Integer getX(){
        return x;
    }
    
    public Integer getY(){
        return y;
    }
    
    public Integer getNum(){
        return num;
    }
    
    public Node getRight(){
        return right;
    }
    
    public Node getLeft(){
        return left;
    }
}

class Solution {
    public ArrayList<Integer> preorder, postorder;
    
    public void pre(Node now){
        if(now==null)
            return;
        
        preorder.add(now.getNum());
        pre(now.getLeft());
        pre(now.getRight());
    }
    
    public void post(Node now){
        if(now == null)
            return;
        
        post(now.getLeft());
        post(now.getRight());
        postorder.add(now.getNum());
    }
    
    
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][nodeinfo.length];
        preorder = new ArrayList<>();
        postorder = new ArrayList<>();
        
        Node[] nodes = new Node[nodeinfo.length];
        
        for(int i=0;i<nodeinfo.length;i++){
            nodes[i] = new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]);
        }
        
        Arrays.sort(nodes,new Comparator<Node>(){
            @Override
            public int compare(Node a, Node b){
                if(a.getY()==b.getY()){
                    return Integer.compare(a.getX(),b.getX());
                }
                return Integer.compare(b.getY(),a.getY());
            }
        });
        
        Node head = nodes[0];
        
        for(int i=1;i<nodes.length;i++){
            head = nodes[0];
            while(true){
                if(head.getX()<nodes[i].getX()){
                    if(head.getRight() == null){
                        head.setRight(nodes[i]);
                        break;
                    }
                    head = head.getRight();
                }
                else{
                    if(head.getLeft() == null){
                        head.setLeft(nodes[i]);
                        break;
                    }
                    head = head.getLeft();
                }
            }
        }
        
        pre(nodes[0]);
        post(nodes[0]);
        
        for(int i=0;i<nodes.length;i++){
            answer[0][i] = preorder.get(i);
            answer[1][i] = postorder.get(i);
        }
        
        return answer;
    }
}