프로그래머스 : 길찾기 게임 C++

programmers.co.kr/learn/courses/30/lessons/42892?language=cpp

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

 

풀이 겸 후기

1. 그동안 알고리즘 풀때 포인터를 진짜 거의 안썻는데 이 문제는 포인터 없이는 너무 힘들어서 포인터 공부좀 다시 했다

2. 원래 주어진 벡터를 그냥 index로 치면 몰라도 이건 주어진 노드 정보들을 한번 sort하고 트리 구성하는거라 이게 훨씬 편하더라

 

1) 노드 stuct

- 좌표정보랑, 자식 두명 포인터

2) 초기화 과정

3) 좌표를 기준으로 이진 트리 형성이니까 미리 sort

 - y 좌표 큰순으로, y좌표 같으면 x가 작은 순

 

4) 트리 만들기

- 화살표 오랫만에 쓰니까 어색하더라 ㅎㅎ

* : 포인터

&: 값의 위치

ex)

int a =3;

int *p =&a;

cout << p <<endl; 주소값 출력

cout << *p << endl; 3 출력

 

 

struct에 포인터로 접근시 ' -> ' 사용

 

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<vector<int>> answer;

struct node{
    int x,y;
    int index;
    node *left, *right;
};

bool cmp(node a, node b)//y좌표 큰순, x좌표 작은 순
{
    if(a.y !=b.y)
        return a.y>b.y;
    else if(a.y == b.y)
        return a.x < b.x;
}

void add_node(node *now, node *me)
{
    if(now->x > me->x)
    {
        if(now->left ==NULL)
            now->left = me;
        else
            add_node(now->left,me);
    }
    else
    {
        if(now->right == NULL)
            now->right = me;
        else
            add_node(now->right,me);
    }
}

void preorder(vector<int>& a, node* now)
{
    if(now == NULL)
        return;
    a.push_back(now->index);
    preorder(a,now->left);
    preorder(a,now->right);
}

void postorder(vector<int>& a, node* now)
{
    if(now == NULL)
        return;
    postorder(a,now->left);
    postorder(a,now->right);
    a.push_back(now->index);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<node> nodes;
    for(int i=0;i<nodeinfo.size();i++)
    {
        node tmp;
        tmp.x = nodeinfo[i][0];
        tmp.y = nodeinfo[i][1];
        tmp.index = i+1;
        tmp.left =NULL;
        tmp.right=NULL;
        nodes.push_back(tmp);
    }
    sort(nodes.begin(),nodes.end(),cmp);
    
    node *root = &nodes[0];
    for(int i=1;i<nodes.size();i++)
    {
        add_node(root,&nodes[i]);
    }
    vector<int> a;
    preorder(a,root);
    answer.push_back(a);
    a.clear();
    
    postorder(a,root);
    answer.push_back(a);
    return answer;
}