[프로그래머스]기둥과 보 설치

시뮬레이션 문제는 있는 그대로 구조를 구현하는게 중요하다는 것을 명심하자

기둥과 보 문제는 다음과 같이 풀이하는데 핵심은 다음과 같다.

1. 주어진 build_frame 배열을 순회하면서 기둥과 보를 설치하는데 check_gidung, check_bo 이 때 함수를 이용해 설치가 가능한지 검사한다.

2. 삭제하지 못하는 경우가 있을 수 있는데 remove_gidung, remove_bo 사용해서 주변의 보와 기둥이 있다면 현재 삭제하려고 하는 것을 제거한 후에도 구조가 유지되는지 확인한다.

최대한 있는 그대로 구현하는 것이 중요하다는 점을 꼭 명심하자

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int MAX = 150;
 
bool gidung[MAX][MAX];
bool bo[MAX][MAX];
 
bool check_gidung(int y, int x, int n) {
    if (y == 0) { return true; }
    if (y > 0 && gidung[y - 1][x]) { return true; }
    if (x > 0 && bo[y][x - 1]) { return true; }
    if (bo[y][x]) { return true; }
    return false;
}
 
bool check_bo(int y, int x, int n) {
    if (y > 0 && gidung[y - 1][x]) { return true; }
    if (y > 0 && x + 1 <= n && gidung[y - 1][x + 1]) { return true; }
    if (x > 0 && x + 1 <= n && bo[y][x - 1] && bo[y][x + 1]) { return true; }
    return false;
}
 
bool remove_gidung(int y, int x, int n) {
    if (bo[y + 1][x] && !check_bo(y + 1, x, n)) { return false; } 
    if (x > 0 && bo[y + 1][x - 1] && !check_bo(y + 1, x - 1, n)) { return false; } 
    if (x + 1 <= n && bo[y + 1][x + 1] && !check_bo(y + 1, x + 1, n)) { return false; } 
    if (y + 1 <= n && gidung[y + 1][x] && !check_gidung(y + 1, x, n)) { return false; } 
    return true;
}
 
bool remove_bo(int y, int x, int n) {
    if (x > 0 && bo[y][x - 1] && !check_bo(y, x - 1, n)) { return false; } 
    if (x + 1 <= n && bo[y][x + 1] && !check_bo(y, x + 1, n)) { return false; } 
    if (x + 1 <= n && gidung[y][x + 1] && !check_gidung(y, x + 1, n)) { return false; } 
    if (gidung[y][x] && !check_gidung(y, x, n)) { return false; } 
    return true;
}
 
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    
    for (int i = 0; i < MAX; i++) {
        fill(gidung[i], gidung[i] + MAX, 0);
        fill(bo[i], bo[i] + MAX, 0);
    }
    
    for (auto &info: build_frame) {
        if (info[2] == 0 && info[3] == 1) {
            if (check_gidung(info[1], info[0], n)) {
                gidung[info[1]][info[0]] = true;
            }
        }
        if (info[2] == 1 && info[3] == 1) {
            if (check_bo(info[1], info[0], n)) {
                bo[info[1]][info[0]] = true;
            }
        }
        if (info[2] == 0 && info[3] == 0) {
            gidung[info[1]][info[0]] = false;
            if (!remove_gidung(info[1], info[0], n)) { gidung[info[1]][info[0]] = true; }
        }
        if (info[2] == 1 && info[3] == 0) {
            bo[info[1]][info[0]] = false;
            if (!remove_bo(info[1], info[0], n)) { bo[info[1]][info[0]] = true; }
        }
    }
 
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (bo[i][j]) { answer.push_back({j, i, 1}); }
            if (gidung[i][j]) { answer.push_back({j, i, 0}); }
        }
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}