[C++/그래프 다루기/프로그래머스 LV.3] 길 찾기 게임

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

프로그래머스

---

x,y 좌표에 따라서 흩어진 노드들을 그래프화 시켜서 전위순회(Preorder), 후위순회(Postorder)을 출력하는 문제입니다.

우선 정렬되어있지 않은 여러 노드들을 하나의 그래프로 완성시키기 위해서 노드를 관리할 수 있는 구조체를 생성했습니다. 해당 과정이 이 문제의 핵심이라고 할 수 있습니다.

struct node
{
    int x,y; //본안의 좌표
    int data; //인덱스
    node* left;
    node* right;
    
    node(int _data, int _x, int _y) : data(_data), x(_x), y(_y)
	{
		left = NULL;
		right = NULL;
	}
};

 

1. 해당 노드의 x,y 좌표

2. nodeInfo 배열에서의 해당 노드 인덱스 정보 (노드번호 순대로 정렬 되어있음)

3. 왼쪽 자식노드 (left), 오른쪽 자식 노드(right)

4. 생성자를 통해 (노드번호, x좌표, y좌표)를 노드 생성자를 통해 입력해주고 자식노드는 NULL로 둡니다.

5. node를 변수로 하는 vector<node>tree 배열을 생성해서 정렬을 해줍니다.

bool compare(node a, node b)
{
    if(a.y==b.y)
        return a.x<b.x;
    else
        return a.y>b.y;
}

y에 대해선 내림차순 x에 대해선 오름차순으로 정렬해줍니다.

 

 

노드 그림

정렬을 하게 되면 vector<int>tree 벡터에 y좌표가 가장큰 순서 && x좌표가 작은 순서로 정렬이 됩니다.

예시 그림에서는 {7,4,2,6,1,3,9,8,5} 노드번호 순으로 정렬됨. 해당 tree배열을 가지고 노드들의 부모 자식 관계를 정해줄 수 있습니다.

 

1. node a, node b 가 있다고 하면 a.y>b.y 이면 a는 b노드보다 항상 상위의 노드입니다.

2. 정렬을 y와 x에 대해서 정렬을 해놨기때문에 tree배열을 반복문으로 돌면서 부모와 자식 관계를 정해줍니다.

void setParent(node* parent, node* child)
{
    if(parent->x > child->x)
    {
        if(parent->left==NULL)
        {
            parent->left = child;
            return;
        }
        setParent(parent->left,child);
    }
    else 
    {
        if(parent->right==NULL)
        {
            parent->right = child;
            return;
        }
        setParent(parent->right,child);
    }
}

 

해당 과정까지 끝났다면 preorder과 postorder를 진행해 최종 결과를 구합니다.

 

전체소스코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#define MAX 10001

using namespace std;

vector<int>graph[MAX];
int n;//노드의 갯수


struct node
{
    int x,y; //본안의 좌표
    int data; //인덱스
    node* left;
    node* right;
    
    node(int _data, int _x, int _y) : data(_data), x(_x), y(_y)
	{
		left = NULL;
		right = NULL;
	}
};
bool compare(node a, node b)
{
    if(a.y==b.y)
        return a.x<b.x;
    else
        return a.y>b.y;
}

void setParent(node* parent, node* child)
{
    if(parent->x > child->x)
    {
        if(parent->left==NULL)
        {
            parent->left = child;
            return;
        }
        setParent(parent->left,child);
    }
    else 
    {
        if(parent->right==NULL)
        {
            parent->right = child;
            return;
        }
        setParent(parent->right,child);
    }
}
void preorder(node* root, vector<int> &pre)
{
    pre.push_back(root->data);
    if(root->left!=NULL)
        preorder(root->left, pre);
    if(root->right!=NULL)
        preorder(root->right, pre);
}

void postorder(node *root, vector<int> &pos)
{
    if(root->left!=NULL)
        postorder(root->left, pos);
    if(root->right!=NULL)
        postorder(root->right, pos);
    pos.push_back(root->data);
}



vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>>answer;
    vector<node>tree;
    
    for(int i=0;i<nodeinfo.size();i++)
    {
        tree.push_back({i+1,nodeinfo[i][0],nodeinfo[i][1]});
    }
    sort(tree.begin(),tree.end(),compare);
    
    // for(int i=0;i<tree.size();i++)
    // {
    //     cout<<tree[i].data<<" "<<tree[i].x<<" "<<tree[i].y<<endl;
    // }
    
    node* root = &tree[0];

    for(int i=1;i<tree.size();i++)
    {
        setParent(root,&tree[i]);
    }
    
    vector<int>answer1; //preorder
    vector<int>answer2; //postorder
    
    preorder(root,answer1);
    //memset(visited,false,sizeof(visited));
    postorder(root,answer2);
    
    answer.push_back(answer1);
    answer.push_back(answer2);
    
    
    
    
    return answer;
}