[알고리즘] 프로그래머스 3단계 - 길 찾기 게임

프로그래머스 문제 링크

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

 

문제 설명

그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 

구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.

nodeInfo 배열가 2차 배열로 주어지는 0번 인덱스는 x좌표 1번 인덱스는 y좌표이다.

y는 노드의 계층을 의미하고 제일 높은 값을 가진 노드가 루트 노드이다.

x는 하위 노드가 좌측이 될지 우측이 될지 정해지는 기준이된다.

즉 y기준으로 노드를 1번째 정렬후 x기준으로 정렬한다음 전위와 후위 순으로 이진트리를 만든다.

 

예시

nodeinfo

[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]

result
[[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

 

import java.util.*;
import java.util.stream.Stream;

public class Main {
	// 노드 정보
    public static int[][] solution(int[][] nodeInfo) {
    	// 노드 정렬, 각 노드 연결
        Node root = makeBT(nodeInfo);
        
        // 전위 정렬
        ArrayList<Integer> preOrderList = new ArrayList<>();
        preOrder(root, preOrderList);

		// 후위 정렬
        ArrayList<Integer> postOrderList = new ArrayList<>();
        postOrder(root, postOrderList);

        int[][] answer = new int[2][nodeInfo.length];
        answer[0] = preOrderList.stream().mapToInt(val -> val).toArray();
        answer[1] = postOrderList.stream().mapToInt(val -> val).toArray();
		return answer;
    }
	
    private static Node makeBT(int[][] nodeInfo) {
    	// 노드에 인덱스 정보와 x, y 값 초기화
        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]);
        }
		
        // y값 기준으로 정렬하되 같은경우 x값으로 정렬
        Arrays.sort(nodes, ((o1, o2) -> {
            if (o1.y == o2.y) {
                return Integer.compare(o1.x, o2.x);
            }
            return Integer.compare(o2.y, o1.y);
        }));
		
        // 루트 노드 설정
        Node root = nodes[0];
		
        // 갖고있는 노드 수만 큼 반복
        for (int i = 1; i < nodes.length; i++) {
        	// 시작은 루트 노드 부터 순회
            Node parent = root;
            
            // 노드 설정하기 전까지 무한 반복
            while (true) {
            	// 노드의 x값이 작은 경우 left 노드 설정
                if (nodes[i].x < parent.x) {
                	// 좌측 노드가 빈 경우 현재 꺼낸 노드를 설정
                    if (parent.left == null) {
                        parent.left = nodes[i];
                        break;
                    } else {
                    	// 좌측 노드가 있는 경우 부모 노드로 설정하고 다시 순회
                        parent = parent.left;
                    }
                } else {
                	// 우측 노드가 빈 경우 현재 꺼낸 노드로 설정
                    if (parent.right == null) {
                        parent.right = nodes[i];
                        break;
                    } else {
                    	// 우측 노드가 있는 경우 부모 노드로 설정하고 다시 순회
                        parent = parent.right;
                    }
                }
            }
        }
        // 설정한 루트 노드 리턴
        return nodes[0];
    }
	
    // 전위 정렬
    public static void preOrder(Node curr, ArrayList<Integer> answer) {
        if (curr == null) {
            return;
        }

        answer.add(curr.idx);
        preOrder(curr.left, answer);
        preOrder(curr.right, answer);

    }

	// 후위 정렬
    public static void postOrder(Node curr, ArrayList<Integer> answer) {
        if (curr == null) {
            return;
        }

        postOrder(curr.left, answer);
        postOrder(curr.right, answer);
        answer.add(curr.idx);
    }
}

class Node {
    int x;

    int y;

    int idx;

    Node left;

    Node right;

    public Node(int idx, int x,int y) {
        this.x = x;
        this.y = y;
        this.idx = idx;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

 

 

이 문제는 보기에 정렬까지는 시도했지만 x값을 기준으로 노드를 분류하는데 힘들어서 책을 참고했다.