[programmers] 길 찾기 게임

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

프로그래머스

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

범위 분할해 재귀 탐색

 

---------------------------------------------------풀이----------------------------------------------------

 

트리를 구성하는 것이 핵심이었던 문제이다.

문제 조건에 맞게, 루트 노드를 잡고 왼쪽, 오른쪽으로 분할하여 각각 재귀적인 방식으로 탐색하였다.

 

좌표로 노드 번호를 찾을 수 있게 map을 사용해 node_num을,

노드 번호로 좌표를 찾을 수 있게 map을 사용해 node_loc을 만들어 각각 nodeinfo에서 가져와 저장하였다.

그 다음, y값이 가장 큰 노드(루트노드)를 구하고, (O(n))

x좌표에 대해 오름차순 정렬하여 nodes_by_x에 노드 번호를 구해 저장한다.

이제 미리 해줄 세팅 작업이 끝난다.

 

make_tree()함수를 재귀적으로 돌며 tree[][]를 구성한다. tree[i][0]은 i번 노드의 왼쪽 child 노드 번호를, tree[i][1]은 i번 노드의 오른쪽 child 노드 번호를 저장할 것이므로, 초기에는 전부 -1을 저장해 없다는 것을 표시한다.

 

make_tree()에는 다음과 같은 인자들을 넘겨준다.

int par : 현재 노드 번호

int cur : nodes_by_x에서의 par의 인덱스

int l : 왼쪽 끝 노드의 nodes_by_x에서의 인덱스

int r : 오른쪽 끝 노드의 nodes_by_x에서의 인덱스 + 1

이 때, cur을 찾기 위해 lower_bound()함수를 이용하였다.

nodes_by_x에서 par이 위치하는 인덱스를 찾아준다.

 

이 재귀 함수에서는 다음과 같은 과정을 반복한다.

par 노드의 아래 level 노드(y가 작은 노드들. 큰 노드들은 전부 이미 처리된 상태일 것임) 중 왼쪽과 오른쪽으로 나누어 각각 제일 큰 y값을 가져와 왼쪽 child, 오른쪽 child로 넣어주고,

그 노드를 par로 보고 다시 child 노드가 없을 때까지 반복한다.

 

이렇게 완성된 tree[][]배열에 대해,

preorder()과 postorder()를 한 번씩 반복한다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>

using namespace std;

// x와 y 기준으로 각각 오름, 내림차순 정렬된 배열.
vector<int> nodes_by_x;
vector<vector<int> > locs_by_x;
// node 번호와 위치를 매칭
map<pair<int,int>, int> node_num; 
pair<int,int> node_loc[10001];
// child를 저장
int tree[10001][2];

// y좌표가 큰 것부터, x좌표가 작은것부터
bool cmp1(vector<int> a, vector<int> b){
    if(a[1] == b[1]){
        return a[0] < b[0];
    }
    return a[1] > b[1];
}
// x좌표가 작은것부터
bool cmp2(vector<int> a, vector<int> b){
    return a[0] < b[0];
}
// binary search에서 x좌표 오름차순으로 정렬된 것으로 보고 비교
bool cmp3(int a, int b){
    return node_loc[a].first < node_loc[b].first;
}

// l이상 r미만의 인덱스 값 중 거기에 해당하는 값의 y가 가장 큰 인덱스 찾기
int get_max_y(vector<vector<int> > arr, int l, int r){
    int maxY = -1, maxIdx = l;
    for(int i = l; i < r; i++){
        if(arr[i][1] > maxY){
            maxY = arr[i][1];
            maxIdx = i;
        }
    }
    return node_num[{arr[maxIdx][0], arr[maxIdx][1]}];
}

// 현재 노드, 현재노드 인덱스, 왼쪽끝노드의 x좌표 순번, 오른쪽끝노드의 x좌표 순번+1
void make_tree(int par, int cur, int l, int r){
    // 자기보다 낮은 level의 노드 중에서 왼쪽, 오른쪽 나누어 트리 구성
    // par 기준 왼쪽 노드 중 y가 가장 큰 값 찾기
    if(l < cur){
        // 다음 노드 번호
        int next = get_max_y(locs_by_x, l, cur);
        tree[par][0] = next;
        // 다시 나누기
        make_tree(next, lower_bound(nodes_by_x.begin()+l, nodes_by_x.begin()+cur, next, cmp3) - nodes_by_x.begin(), l, cur);
    }
    // par 기준 오른쪽 노드 중 y가 가장 큰 값 찾기
    // 없으면 child가 없는 것!
    if(r-1 > cur){
        int next = get_max_y(locs_by_x, cur+1, r);
        tree[par][1] = next;
        // 다시 나누기
        make_tree(next, lower_bound(nodes_by_x.begin()+cur+1, nodes_by_x.begin()+r, next, cmp3) - nodes_by_x.begin(), cur+1, r);
    }
}

// V L R
void preorder(int cur, vector<int> &answer){
    answer.push_back(cur+1);
    if(tree[cur][0] != -1){
        preorder(tree[cur][0], answer);
    }
    if(tree[cur][1] != -1){
        preorder(tree[cur][1], answer);
    }
}

// L R V
void postorder(int cur, vector<int> &answer){
    if(tree[cur][0] != -1){
        postorder(tree[cur][0], answer);
    }
    if(tree[cur][1] != -1){
        postorder(tree[cur][1], answer);
    }
    answer.push_back(cur+1);
}

// 노드는 1~N
// 모두 다른 x값, 자식 노드의 y값은 항상 부모 노드보다 작음.
// 노드의 왼쪽 서브트리에 있는 모든 x값은 이 노드의 x보다 작음.
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer(2);
    // 좌표에 해당하는 노드 저장 => 편의상 0~N-1로 저장.
    for(int i = 0; i < nodeinfo.size(); i++){
        node_num[{nodeinfo[i][0],nodeinfo[i][1]}] = i;
        node_loc[i] = {nodeinfo[i][0],nodeinfo[i][1]};
    }
    // y값이 가장 큰 노드를 찾아 par에 저장(루트노드)
    int par = get_max_y(nodeinfo, 0, nodeinfo.size());
    // x좌표가 작은것부터 정렬.
    sort(nodeinfo.begin(), nodeinfo.end(), cmp2);
    for(int i = 0; i < nodeinfo.size(); i++){
        nodes_by_x.push_back(node_num[{nodeinfo[i][0],nodeinfo[i][1]}]);
    }
    locs_by_x = nodeinfo;
    // 초기화
    for(int i = 0; i < node_num.size(); i++){
        tree[i][0] = tree[i][1] = -1;
    }
    make_tree(par, lower_bound(nodes_by_x.begin(), nodes_by_x.end(), par, cmp3) - nodes_by_x.begin(), 0, nodeinfo.size());
    
    preorder(par, answer[0]);
    postorder(par, answer[1]);
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

x로 오름차순 정렬된 노드들 중에서, y값이 가장 큰 노드를 찾을 때

처음에는 y값대로 내림차순 정렬 후 제일 앞의 값을 가져오는 방식으로 구현하였다.

이렇게하니 70점대를 받은... 그런데 생각해보니 이럴 필요가 없었다!!

시간초과로 실패한 것인데,

생각해보면 기존 벡터를 복사하는데도 시간이 걸리고,

벡터를 정렬하는 데 sort()를 사용했으니 평균 O(nlogn), 최대 O(n^2)이 걸린다.

최댓값만 찾을 거라면, 단순히 비교해서 가져와도 되니까 선형 비교를 하면 O(n)밖에 안걸린다.

이걸 매번 반복해야 하므로, 사실 트리의 최대 depth가 1000이랬으니, 생각보다 큰 차이....

 

그래서 이걸 고치니까 89점인가 받았는데, 바로 실패 뜨거나 시간초과가 빠르게 나는 걸로 봐선 뭔가 오류가 있는 것 같았다.

바로 x,y 좌표가 0이상이라는 점!

get_max_y()함수에서 maxY의 초기값을 0으로 두고 했더니 발생한 문제이다.

따라서 -1부터 시작해 비교했더니 통과할 수 있었다.

 

+ 더 빠를 것 같은 풀이!

heap을 구성할 때처럼, 각 노드를 배열로 저장해 트리를 만들어 탐색하는 방법.

이 1차원 배열의 특징은 n의 child 노드가 n*2, n*2+1에 들어있다는 점이다.

이 트리를 구성하기 위해 우선,

처음 nodeinfo 배열을 y값에 대해 내림차순으로, y가 같을 경우 x에 대해 오름차순으로 정렬한다. (nlogn)

다음으로,

이 배열을 순서대로 돌면서, 어디에 들어갈지를 판단해준다. (판단 과정은 아래 순서대로 서술하였다.)

예를 들어 문제에 나온 예시에서, 

위에서 설명한 방식대로 정렬하면 arr[]는 '7, 4, 2, 6, 1, 3, 9, 8, 5' 가 된다.

**여기서는 편의상 인덱스가 1부터 시작한다고 가정한다.

  1. 트리 배열의 초기 상태 : tree[] = {-1, -1, -1, -1, -1, -1, -1, -1, -1} | arr[1] : 7, {8,6}

tree[1]가 비어있으므로 그 자리에 arr[1]를 채워넣는다.

  2. tree[] = {7, -1, -1, -1, -1, -1, -1, -1, -1} | arr[2] : 4, {3,5}

tree[1]=7{8,6}보다 왼쪽에 있으므로 왼쪽 child 노드를 본다.

이 때, tree[1*2]가 비어있으므로 4를 넣는다.

  3. tree[] = {7, 4, -1, -1, -1, -1, -1, -1, -1} | arr[3] : 2, {11,5}

tree[0]=7{8,6}보다 오른쪽에 있으므로 오른쪽 child 노드를 본다.

이 때, tree[1*2+1]가 비어있으므로 2를 넣는다.

  4. tree[] = {7, 4, 2, -1, -1, -1, -1, -1, -1} | arr[4] : 6, {1,3}

tree[0]=7{8,6}보다 왼쪽에 있으므로 왼쪽 child 노드를 본다.

tree[1*2]=tree[2]=4{3,5}보다 왼쪽에 있으므로 왼쪽 child 노드를 본다.

tree[2*2]가 비었으므로 6을 넣어준다.

  5. tree[] = {7, 4, 2, 6, -1, -1, -1, -1, -1} | arr[5] : 1, {5,3}

tree[0]=7{8,6}보다 왼쪽에 있으므로 왼쪽 child 노드를 본다.

tree[1*2]=tree[2]=4{3,5}보다 오른쪽에 있으므로 오른쪽 child 노드를 본다.

tree[2*2+1]가 비었으므로 1을 넣어준다.

  6. tree[] = {7, 4, 2, 6, 1, -1, -1, -1, -1} | arr[6] : 3, {13,3}

tree[0]=7{8,6}보다 오른쪽에 있으므로 오른쪽 child 노드를 본다.

tree[1*2+1]=tree[3]=2{11,5}보다 오른쪽에 있으므로 오른쪽 child 노드를 본다.

tree[3*2+1]가 비었으므로 3을 넣어준다.

  7. tree[] = {7, 4, 2, 6, 1, -1, 3, -1, -1} | arr[7] : 9, {2,2}

tree[0]=7{8,6}보다 왼쪽에 있으므로 왼쪽 child 노드를 본다.

tree[1*2]=tree[2]=4{3,5}보다 왼쪽에 있으므로 왼쪽 child 노드를 본다.

tree[2*2]=tree[4]=6{1,3}보다 오른쪽에 있으므로 오른쪽 child 노드를 본다.

tree[4*2+1]가 비었으므로 9를 넣어준다.

  8. tree[] = {7, 4, 2, 6, 1, -1, 3, -1, 9} | arr[8] : 8, {7,2}

tree[0]=7{8,6}보다 왼쪽에 있으므로 왼쪽 child 노드를 본다.

tree[1*2]=tree[2]=4{3,5}보다 오른쪽에 있으므로 오른쪽 child 노드를 본다.

tree[2*2+1]=tree[5]=1{5,3}보다 오른쪽에 있으므로 오른쪽 child 노드를 본다.

tree[5*2+1]가 비었으므로 8을 넣어준다.

  9. tree[] = {7, 4, 2, 6, 1, -1, 3, -1, 9, -1, 8} | arr[9] : 5, {6,1}

tree[0]=7{8,6}보다 왼쪽에 있으므로 왼쪽 child 노드를 본다.

tree[1*2]=tree[2]=4{3,5}보다 오른쪽에 있으므로 오른쪽 child 노드를 본다.

tree[2*2+1]=tree[5]=1{5,3}보다 오른쪽에 있으므로 오른쪽 child 노드를 본다.

tree[5*2+1]=tree[11]=8{7,2}보다 왼쪽에 있으므로 왼쪽 child 노드를 본다.

tree[11*2+1]가 비었으므로 5를 넣어준다.

 

최종 트리 형태 : tree[] = {7, 4, 2, 6, 1, -1, 3, -1, 9, -1, 8, -1, -1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1, -1, 5}

이제 순회 방식에 따라 탐색하면 된다!