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

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

프로그래머스

 

동일한 지점에 보와 기둥이 두개다 설치될수도있으므로, 보와 기둥을 따로 bool배열로 저장한다.

추가할때는 해당 셀이 유효한지 검사하면되고, 삭제할때는 삭제한 뒤에도 모든 셀이 유효한지를 검사해야한다.

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

bool pillar[101][101];
bool beam[101][101];

bool canPillar(int x, int y) {
    return y == 0 || pillar[x][y - 1] || beam[x][y] || (x > 0 && beam[x - 1][y]);
}

bool canBeam(int x, int y) {
    return (pillar[x][y - 1] || pillar[x + 1][y - 1]) || (beam[x - 1][y] && beam[x + 1][y]);
}

bool isValid(int n) {
    for (int x = 0; x <= n; x++) {
        for (int y = 0; y <= n; y++) {
            if (pillar[x][y] && !canPillar(x, y)) return false;
            if (beam[x][y] && !canBeam(x, y)) return false;
        }
    }
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    for (auto& cmd : build_frame) {
        int x = cmd[0], y = cmd[1], kind = cmd[2], op = cmd[3];
        if (op == 1) { // 설치
            if (kind == 0) { // 기둥
                pillar[x][y] = true;
                if (!canPillar(x, y)) pillar[x][y] = false;
            } else { // 보
                beam[x][y] = true;
                if (!canBeam(x, y)) beam[x][y] = false;
            }
        } else { // 삭제
            if (kind == 0) pillar[x][y] = false;
            else beam[x][y] = false;
            
            if (!isValid(n)) { // 구조 무너지면 복구
                if (kind == 0) pillar[x][y] = true;
                else beam[x][y] = true;
            }
        }
    }
    
    vector<vector<int>> answer;
    for (int x = 0; x <= n; x++) {
        for (int y = 0; y <= n; y++) {
            if (pillar[x][y]) answer.push_back({x, y, 0});
            if (beam[x][y]) answer.push_back({x, y, 1});
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}