[C++] 프로그래머스 길 찾기 게임 풀이

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

코딩테스트 연습 - 길 찾기 게임

문제 설명

이 문제는 좌표로 주어지는 노드들을 트리로 이진 트리로 만들어 전위 순회, 후위 순회 결과를 리턴하는 문제이다. 예시는 다음과 같다.

문제 예시

첫 번째 그림과 같이 주어진 좌표를 아래의 그림처럼 이진 트리 구조로 만드는 것이다. 트리를 구성하는 노드들의 규칙은 다음과 같다.

1. 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
2. 모든 노드는 서로 다른 x값을 가진다.
3. 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
4. 자식 노드의 y 값은 항상 부모 노드보다 작다.
5. 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
6. 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

위 예시의 전위 순회와 후위 순회의 결과는 다음과 같이 나온다.

• 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
• 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

 

풀이

이 문제를 풀기 위해서 우선 트리를 구현해야한다. 연결리스트를 이용하여 구현하면 복잡해진다고 판단하여 배열을 이용하였다.

 

1. 트리의 표현

    pair<int,int>로 구성된 배열을 이용하여 first에는 왼쪽 자식, second에는 오른쪽 자식의 번호를 저장하였다. 트리를 사용하기 위해서는 트리를 초기화해야한다. 자식을 가리키는 인덱스 번호가 자기 자신과 같다면 리프노드로 판단하도록 초기화하였다.

 

2. 노드 순서

    입력으로 주어진 노드 정보들을 루트 노드부터 순서대로 정렬해야한다. 이때 주어진 배열의 (인덱스 번호 + 1)이 노드의 번호이기 때문에 주어진 배열 자체를 정렬시키면 안되고 인덱스 번호와 좌표를 유지해야한다. 따라서 각 노드의 번호를 통해 좌표를 쉽게 찾기 위해 map을 사용하였고 전위 순회 방식으로 노드를 정렬하기 위해 정렬을 위한 node라는 배열을 따로 선언하였다.

 

3. 트리 구현

    그 다음에는 정렬된 노드를 순서대로 트리에 붙여나가야한다. 트리를 만드는 find함수를 따로 구현하였다. find 함수는 다음과 같이 동작한다.

1. 현재 노드의 x좌표보다  추가하는 노드의 x좌표가 작은 경우(왼쪽 자식인 경우)
   • 만약 왼쪽 자식이 자기 자신일 때(리프노드일 때) 왼쪽 자식에 붙인다.
   • 그렇지 않으면 재귀적으로 왼쪽 자식과 현재 노드를 방금 과정과 똑같이 비교한다.
2. 현재 노드의 x좌표보다 추가하는 노드의 x좌표가 큰 경우(오른쪽 자식인 경우)
   • 만약 오른쪽 자식이 자기 자신일 때(리프노드일 때) 오른쪽 자식에 붙인다.
   • 그렇지 않으면 재귀적으로 오른쪽 자식과 현재 노드를 방금 과정과 똑같이 비교한다.

4. 전위 순회와 후위 순회

    전위 순회는 왼쪽 오른쪽 자식을 탐색하기 전에 자기 자신을 경로에 넣으면 된다. 반대로 후위 순회는 왼쪽 오른쪽 자식을 탐색하고 난 이후에 자기 자신을 경로에 넣으면 된다.

 

소스코드

 

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

using namespace std;

pair<int,int> tree[10001];
map<int,pair<int,int>> m;

vector<int> frontpath; //전위순회 경로
vector<int> endpath; //후위순회 경로

struct edge { //정렬을 위한 구조체
    int idx, x, y;
};

bool cmp(edge a, edge b) { //루트노드부터 순서대로 정렬하는 비교함수
    if(a.y == b.y) {
        return a.x < b.x;
    }
    else
        return a.y > b.y;
}

void find(int now, edge e) { //적절한 위치 찾기
    pair<int,int> nowpos = m[now];
    if(nowpos.first > e.x) { //왼쪽자식인 경우
        if(tree[now].first == now) { //왼쪽 자식 끝인 경우
            tree[now].first = e.idx; //왼쪽 자식에 붙이기
            return;
        }
        else { //끝이 아닌 경우
            find(tree[now].first, e); //재귀적으로 탐색
        }
    }
    else { //오른쪽 자식인 경우
        if(tree[now].second == now) { //오른쪽 자식 끝인 경우
            tree[now].second = e.idx;
            return;
        }
        else {
            find(tree[now].second, e);
        }
    }
    return;
}

void front(int now) { //전위순회
    frontpath.push_back(now); //경로 먼저 추가
    if(tree[now].first != now) { //리프노드가 아니라면
        front(tree[now].first); //왼쪽 자식 탐색
    }
    if(tree[now].second != now) {//리프노드가 아니라면
        front(tree[now].second); //오른쪽 자식 탐색
    }
}

void end(int now) { //후위순회
    if(tree[now].first != now) { //리프노드가 아니라면
        end(tree[now].first); //왼쪽 자식 탐색
    }
    if(tree[now].second != now) { //리프노드가 아니라면
        end(tree[now].second); //오른쪽 자식 탐색
    }
    endpath.push_back(now); //경로 나중에 추가
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    vector<edge> node; //정렬을 위한 배열
    
    for(int i = 1; i <= nodeinfo.size(); i++) { //트리 초기화
        tree[i].first = i; //왼쪽 자식을 자기 자신으로
        tree[i].second = i; //오른쪽 자식을 자기 자신으로
    }
    
    for(int i = 0;i < nodeinfo.size(); i++) { 
        node.push_back({i+1, nodeinfo[i][0], nodeinfo[i][1]}); //정렬을 위한 배열
        m[i+1] = {nodeinfo[i][0], nodeinfo[i][1]}; //각 노드 번호별 x, y좌표 map에 저장
    }
    sort(node.begin(), node.end(), cmp); //y좌표가 큰순, x좌표가 작은순으로 정렬
    
    int root = node[0].idx; //루트 인덱스 번호
    
    for(int i = 1; i < node.size(); i++) {
        edge now = node[i]; //현재 노드
        find(root, now); //자식으로 붙이기
    }
    
    front(root); //전위순회
    end(root); //후위순회
    
    
    answer.push_back(frontpath);
    answer.push_back(endpath);
    
    return answer;
}

 

결과