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

문제 설명

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

문제 풀이

• 기본 그래프 이론과 재귀를 이용해여 풀이하였다.

• 풀이 순서는 다음과 같다.
  1. 이진 트리 만들기
  2. 전위 순회, 후위 순회 결과 생성

• 이중 이진 트리를 만드는 과정은 다음과 같다.

  • 주어진 노드들을 x좌표 기준 정렬한다.
  • Node divide (int s, int e)
    - 위 정렬된 배열에서 인덱스 s ~ e까지 y가 가장큰 노드 A 선택
    - divide(s, A 인덱스 - 1) 결과는 A의 좌측 자식으로 지정
    - divide(A 인덱스 - 1, e) 결과는 A의 우측 자식으로 지정
    - A 리턴

• 전위 순회, 후위 순회 코드는 아래를 참조하면 된다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public class Node implements Comparable<Node>{
        public int n, x, y;
        Node left, right;
        public Node(int n, int x, int y) {
            this.n = n;
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Node o) {
            return this.x - o.x;
        }
    }
    public int N, ind;
    public Node[] nodeInfo;
    public int[] pre, post;

    //(s, e) 구간에서 y가 가장 큰 노드 리턴 및 이진 트리 생성
    public Node divide(int s, int e) {
        if (s == e) return nodeInfo[s];
        //y가 가장 큰 노드 찾기
        int maxNodeInd = 0;
        int maxY = -1;
        for (int i = s; i <= e; i++) {
            if (maxY < nodeInfo[i].y) {
                maxNodeInd = i;
                maxY = nodeInfo[i].y;
            }
        }
        Node maxNode = nodeInfo[maxNodeInd];

        //좌측 이동
        if (maxNodeInd != s)
            maxNode.left = divide(s, maxNodeInd - 1);
        //우측 이동
        if (maxNodeInd != e)
            maxNode.right = divide(maxNodeInd + 1, e);
        return maxNode;
    }

    //전위 순회
    public void preOrder(Node node) {
        if (node == null) return;
        pre[ind++] = node.n;
        preOrder(node.left);
        preOrder(node.right);
    }

    //후위 순회
    public void postOrder(Node node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        post[ind++] = node.n;
    }

    public int[][] solution(int[][] nodeinfo) {
        //초기화
        N = nodeinfo.length;
        nodeInfo = new Node[N];
        for (int i = 0; i < N; i++) {
            int x = nodeinfo[i][0];
            int y = nodeinfo[i][1];
            nodeInfo[i] = new Node(i+1, x, y);
        }
        Arrays.sort(nodeInfo); //x 순으로 정렬

        //이진 트리 생성
        Node root = divide(0, N - 1);

        //결과 생성
        pre = new int[N];
        post = new int[N];
        ind = 0;
        preOrder(root);
        ind = 0;
        postOrder(root);
        return new int[][] {pre, post};
    }
}