알고리즘/프로그래머스

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

쿠큭다스 2023. 9. 23. 17:26
728x90

 

문제설명

 

 

풀이방법

 

해당 문제를 풀기 위해서는 이진트리의 순회방법을 살펴볼 필요가 있다.

- 전위순회(preOrder) : 루트(root) 방문 -> 왼쪽 자식노드 -> 오른쪽 자식노드

- 중위순회(inOrder) : 왼쪽 자식노드 방문 -> 루트(root) -> 오른쪽 자식노드

- 후위순회(postOrder) : 왼쪽 자식노드 방문 -> 오른쪽 자식노드 -> 루트(root)

 

-> 순회방법의 앞글자인 전, 중, 후는 각각 루트노드의 방문 순서를 나타냄

 

문제의 조건인, '자식의 y값은 부모의 y값보다 작다'이므로 y값이 큰 순서대로 트리에 삽입이므로 정렬

 

구현코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.*;
 
class Solution {
    
    int[][] answer = {};
    int idx;
    
    public int[][] solution(int[][] nodeinfo) {
        
        Node node[]=new Node[nodeinfo.length];
        for(int i=0;i<nodeinfo.length;i++){
            node[i]=new Node(nodeinfo[i][0],nodeinfo[i][1],i+1,null,null);
        }
        
        Arrays.sort(node, new Comparator<Node>(){
           public int compare(Node n1, Node n2){
               if(n1.y==n2.y) return n1.x-n2.x;
               else return n2.y-n1.y;
           } 
        });
        
        Node root=node[0];
        for(int i=1;i<node.length;i++){
            insertNode(root,node[i]);
        }
        
        answer=new int[2][node.length];
        idx=0;
        preOrder(root);
        
        idx=0;
        postOrder(root);
        
        return answer;
    }
    
    public void preOrder(Node root){
        if(root!=null){
            answer[0][idx++]=root.value;
            preOrder(root.left);
            preOrder(root.right);
        }      
    }
    
    public void postOrder(Node root){
        if(root!=null){
            postOrder(root.left);
            postOrder(root.right);
            answer[1][idx++]=root.value;
        }
    }
    
    public void insertNode(Node parent, Node child){
        if(parent.x>child.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);
        }
    }
    
    public class Node{
        int x;
        int y;
        int value;
        Node left;
        Node right;
    
        public Node(int x, int y, int value, Node left, Node right){
            this.x=x;
            this.y=y;
            this.value=value;
            this.left=left;
            this.right=right;
        }
    }
}
 
  

 

 

728x90