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

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

프로그래머스

 

못 푼 이유

Node를 만들어 compareTo override로 정렬 기준까지는 잘만들었지만 별생각없이 TreeSet에 집어넣어서 풀려고 했고, 결과적으로

TreeSet자료구조로는 DFS를 구현할 수 없었다. 

위를 깨닫고 다음번엔 Node배열을 만들어 부모-자식 간 y값의 규칙을 통해 순회하려고 했으나, 규칙을 잘못파악해 성공하지 못했다.

그 후 검색을 통해 만든 Node들을 연결하는 코드를 발견했고 풀 수 있었다.

 

코드 참고

https://code-lab1.tistory.com/131

[프로그래머스] 카카오_길찾기 게임 (자바 풀이)

 

풀이 로직

1. nodeinfo를 node로 만들어 배열에 삽입
2. node배열 정렬
3. node간 연결(insertNode)
4. 전위 순회 구현(preOrder)
5. 후위 순회 구현(postOrder)

이 중 3의 코드가 신박했다.

루트를 제외한 모든 node를 돌며 자식으로 삽입하는 로직인데, 부모노드보다 x가 작으면 leftChild, 크면 rightChild로 삽입. 단, 이미 부모노드에 자식이 존재하는경우 그 자식node의 left || right로 삽입. 그 자식도 자식이 있다면 그 자식의 left||right로 삽입하도록 재귀로 구현한 코드였다.

막상 부모-자식을 연결하라고 해도 구현못했을 것 같은데 좋은 레퍼런스가 된 것 같다.

 

정답 코드 - 전역 index변수와 배열을 이용한 answer append

import java.util.*;

class Solution {
    private int idx;
    int[][] answer;
    
    public int[][] solution(int[][] nodeinfo) {
        answer = new int[2][nodeinfo.length];
        Node[] nodes = new Node[nodeinfo.length];
        
        for(int i=0; i<nodeinfo.length; i++){
            nodes[i] = new Node(i+1, null, null, nodeinfo[i][0], nodeinfo[i][1]);
        }
        
        Arrays.sort(nodes, (e1,e2)->{
            if(e1.y==e2.y){
                return e1.x-e2.x;
            }
            return e2.y-e1.y;
        }
        );
        
        Node root = nodes[0];
        for(int i=1; i<nodes.length; i++){
            insertNode(root, nodes[i]);
        }
        
        preOrder(root);
        idx=0;
        postOrder(root);
        
        return answer;
    }
    
    private void insertNode(Node parent, Node child){
        if(parent.x > child.x){
           if(parent.leftChild==null){
               parent.leftChild = child;
           }else{
               insertNode(parent.leftChild, child);
           } 
        } else{
            if(parent.rightChild==null){
                parent.rightChild=child;
            }else{
                insertNode(parent.rightChild, child);
            }
        }
    }
    
    private void preOrder(Node currentNode){
        answer[0][idx++]=currentNode.value;
        
        if(currentNode.leftChild!=null){
            preOrder(currentNode.leftChild);
        }
        if(currentNode.rightChild!=null){
            preOrder(currentNode.rightChild);
        }
    }    
    
    private void postOrder(Node currentNode){
        if(currentNode.leftChild!=null){
            postOrder(currentNode.leftChild);
        }
        if(currentNode.rightChild!=null){
            postOrder(currentNode.rightChild);
        }
        
        answer[1][idx++]=currentNode.value;
    }
    
    class Node{
        public int value;
        public Node leftChild;
        public Node rightChild;
        public int x;
        public int y;
        
        Node(int value, Node leftChild, Node rightChild, int x, int y){
            this.value=value;
            this.leftChild=leftChild;
            this.rightChild = rightChild;
            this.x=x;
            this.y=y;
        }
    }
}

import java.util.*;

class Solution {
    List<Integer> preOrderResult = new ArrayList<>();
    List<Integer> postOrderResult = new ArrayList<>();
    
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][nodeinfo.length];
        Node[] nodes = new Node[nodeinfo.length];
        
        for(int i=0; i<nodeinfo.length; i++){
            nodes[i] = new Node(i+1, null, null, nodeinfo[i][0], nodeinfo[i][1]);
        }
        
        Arrays.sort(nodes, (e1,e2)->{
            if(e1.y==e2.y){
                return e1.x-e2.x;
            }
            return e2.y-e1.y;
        }
        );
        
        Node root = nodes[0];
        for(int i=1; i<nodes.length; i++){
            insertNode(root, nodes[i]);
        }
        
        preOrder(root);
        postOrder(root);
        
        Integer[] preOrderArr = preOrderResult.toArray(new Integer[0]);
        answer[0] = Arrays.stream(preOrderArr).mapToInt(Integer::intValue).toArray();
        
        Integer[] postOrderArr = postOrderResult.toArray(new Integer[0]);
        answer[1] = Arrays.stream(postOrderArr).mapToInt(Integer::intValue).toArray();
        
        return answer;
    }
    
    private void insertNode(Node parent, Node child){
        if(parent.x > child.x){
           if(parent.leftChild==null){
               parent.leftChild = child;
           }else{
               insertNode(parent.leftChild, child);
           } 
        } else{
            if(parent.rightChild==null){
                parent.rightChild=child;
            }else{
                insertNode(parent.rightChild, child);
            }
        }
    }
    
    private void preOrder(Node currentNode){
        preOrderResult.add(currentNode.value);
        
        if(currentNode.leftChild!=null){
            preOrder(currentNode.leftChild);
        }
        if(currentNode.rightChild!=null){
            preOrder(currentNode.rightChild);
        }
    }    
    
    private void postOrder(Node currentNode){
        if(currentNode.leftChild!=null){
            postOrder(currentNode.leftChild);
        }
        if(currentNode.rightChild!=null){
            postOrder(currentNode.rightChild);
        }
        
        postOrderResult.add(currentNode.value);
        
    }
    
    class Node{
        public int value;
        public Node leftChild;
        public Node rightChild;
        public int x;
        public int y;
        
        Node(int value, Node leftChild, Node rightChild, int x, int y){
            this.value=value;
            this.leftChild=leftChild;
            this.rightChild = rightChild;
            this.x=x;
            this.y=y;
        }
    }
}

 

배운 점

• comparator 람다 또는 compareTo구현를 통한 정렬
• 트리를 탐색하는 문제는 직접 트리를 만들어 연결하는 게 필요하다. 이진트리의 경우 Node클래스에 left, right필드를 만들어 쓰자. 기존 자료구조만을 사용해서 DFS를 구현할 수 없다. (TreeSet, TreeMap은 poll해도 정렬상태를 유지해야할 때 사용하자)
• Integer[] -> int[] 메서드 정리 게시물에 정리함.