22.06.09. 풀었던 문제들

1. 길 찾기 게임

트리 구현이다. 오랜만에 이런 것 구현할려니까 까먹은 게 많다.

먼저 높이가 높은 순대로 map<int, vector<pii>>에 저장. 이렇게 저장한 map에서 key가 높은 것부터 tree에 넣을 것임. 유의할 점은 node 할당 시 node *root = new node를 써야 한다는 점. 그리고 현재 보고 있는 node의 x값이 parent보다 작으면 왼쪽, 크면 오른쪽에 넣는 binary tree의 삽입 방식을 이용해서 tree에 계속 넣어준다. 만약 parent->child가 NULL이면 그 부분에 cur_node를 넣어주면 된다.

이렇게 tree를 만들었으면 traversal이다. preorder는 값 넣은 이후 탐색이고, postorder는 탐색 이후 값 넣기이다.

구현이 귀찮은 문제였다.

// 길 찾기 게임

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

using namespace std;

struct node{
    node *left, *right, *parent;
    int x, num;
};

typedef pair<int, int> pii;

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

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

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    
    map<int, vector<pii>, greater<int>> node_per_floor; // node_per_floor[i] : i번째 층의 노드 vector
                                          // .first : 노드 x좌표, .second : 노드 번호
    // i번째 층에 해당하는 node를 뽑기 위함
    for(int i = 0; i<nodeinfo.size(); i++){
        node_per_floor[nodeinfo[i][1]].push_back({nodeinfo[i][0], i+1});
    }
    
    map<int, vector<pii>>::iterator iter = node_per_floor.begin();
    int rootnum = (iter->second)[0].second; // root의 번호
    node *root = new node; root->parent=root; root->left = root->right = NULL; root->x=(iter->second)[0].first; root->num=rootnum; // root node 초기화
    
    for(iter++; iter != node_per_floor.end(); iter++){
        for(pii each_node : iter->second){
            node *parent = root;
            node *cur_node = new node; cur_node->x = each_node.first; cur_node->num = each_node.second; cur_node->left = cur_node->right = NULL; // cur node 초기화
            while(1){
                if(cur_node->x < parent->x){
                    if(parent->left == NULL){
                        parent->left = cur_node;
                        cur_node->parent = parent;
                        break;
                    } else{
                        parent = parent->left;
                    }
                } else if(cur_node->x > parent->x){
                    if(parent->right == NULL){
                        parent->right = cur_node;
                        cur_node->parent=parent;
                        break;
                    } else{
                        parent = parent->right;
                    }
                }
            }
        }
    }
    
    vector<int> preorder_result, postorder_result;
    preorder(root, preorder_result);
    postorder(root, postorder_result);
    vector<vector<int>> answer = {preorder_result, postorder_result};
    return answer;
}
// root는 쉽게 정할 수 있음
// root 아래도 쉽게 정할 수 있음(root보다 작은 값 : root left, root보다 큰 값 : root right)
// 어떤 점 탐색 시 - root부터 탐색, 
// 어떤 vertex보다 왼쪽 - 왼쪽으로 내려감, 오른쪽 - 오른쪽으로 내려감

 

2. 기둥과 보 설치

board size는 100 * 100, 입력은 1000 이하이므로 brute-force 하게 풀어도 10,000,000 이므로 충분히 풀 수 있다. 최적화를 위해서라면 보/기둥 * 설치/삭제 2 * 2의 경우의 수에 대한 예외처리를 모두 해 주어야 겠지만 실제 코테에서 이런 것을 따질 시간은 없을 것 같다. 그래서 naive하게 설치/삭제 시 전체 건물이 안정적인지 검사를 하고(이렇게 한다면 문제에서 주어진 조건만 사용해도 된다 그렇지 않다면 rollback하는 방식으로 구현한다면 좀 더 쉽게 풀 수 있다.