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

프로그래머스

 

 

 

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

using namespace std;

/*
[x, y, a, b]
x, y는 기둥 또는 보를 설치할 교차점의 좌표
a = 0은 기둥, 1은 보
b = 0은 삭제, 1은 설치
구조물은 좌표 기준 보는 오른쪽, 기둥은 위쪽으로 설치

설치 조건
기둥은 바닥 위, 보의 한쪽 끝 부분, 기둥 위에 있어야함
보는 한쪽 끝 부분이 기둥 위에 있거나 양쪽 끝 부분이 다른 보와 연결되어 있어야함
 + 구조물이 겹치도록 설치되는 경우는 주어지지 않음

삭제 조건
삭제한 후에도 남은 기둥과 보들이 설치 조건을 만족한 상태여야 삭제 가능
 + 없는 기둥을 삭제하는 경우는 주어지지 않음
 
정렬 조건
x 좌표 기준 오름차순 정렬, x 좌표가 같으면 y 좌표 기준 오름차순 정렬
x, y 동일 시 기둥이 보보다 앞으로
*/

int N;
bool Pillar[101][101];
bool Beam[101][101];

struct STRUCTURE {
    int x;
    int y;
    int type;
    bool isDeleted;
};

vector<STRUCTURE> list;

// 기둥 설치 가능 여부
bool checkDeployPillar(int x, int y) {
    // 바닥이면
    if(x == N) return true;
    // 보의 오른쪽에 설치할 때
    if(Beam[x][y - 1] && y >= 1) return true;
    // 보의 왼쪽에 설치할 때
    if(Beam[x][y]) return true;
    // 기둥 위에 설치할 때
    if(Pillar[x + 1][y]) return true;
    
    return false;
}

// 보 설치 가능 여부
bool checkDeployBeam(int x, int y) {
    // 왼쪽 끝에 기둥이 있을 때
    if(Pillar[x + 1][y]) return true;
    // 오른쪽 끝에 기둥이 있을 때
    if(Pillar[x + 1][y + 1] && y + 1 <= N) return true;
    // 양쪽 끝에 보가 있을 때
    if(Beam[x][y - 1] && Beam[x][y + 1]) return true;
    
    return false;
}

// 기둥 삭제 가능 여부
void DeletePillar(int x, int y) {
    int idx = 0;
    // 해당 기둥이 설치되지 않음을 가정
    Pillar[x][y] = false;
    
    for(int i = 0; i < list.size(); i++) {
        int curX = list[i].x;
        int curY = list[i].y;
        int Type = list[i].type;
        
        // 현재 구조물이 삭제하려는 기둥과 같다면
        if(x == curX && y == curY && Type == 0) {
            idx = i;
            continue;
        }
        
        // 이미 삭제된 구조물이면
        if(list[i].isDeleted) 
            continue;
        
        // 리스트에 있는 기둥 중 설치가 불가능한 기둥이 나온다면
        if(Type == 0 && checkDeployPillar(curX, curY) == false) {
            Pillar[x][y] = true;
            return;
        }
        
        // 리스트에 있는 보 중 설치가 불가능한 보가 나온다면
        if(Type == 1 && checkDeployBeam(curX, curY) == false) {
            Pillar[x][y] = true;
            return;
        }
    }
    
    list[idx].isDeleted = true;
}

// 보 삭제 가능 여부
void DeleteBeam(int x, int y) {
    int idx = 0;
    // 해당 보가 설치되지 않았음을 가정
    Beam[x][y] = false;
    
    for(int i = 0; i < list.size(); i++) {
        int curX = list[i].x;
        int curY = list[i].y;
        int Type = list[i].type;
        
        // 현재 구조물이 삭제하려는 보과 같다면
        if(x == curX && y == curY && Type == 1) {
            idx = i;
            continue;
        }
        
        // 이미 삭제된 구조물이면
        if(list[i].isDeleted) 
            continue;
        
        // 리스트에 있는 기둥 중 설치가 불가능한 보가 나온다면
        if(Type == 0 && !checkDeployPillar(curX, curY)) {
            Beam[x][y] = true;
            return;
        }
        
        // 리스트에 있는 보 중 설치가 불가능한 보가 나온다면
        if(Type == 1 && !checkDeployBeam(curX, curY)) {
            Beam[x][y] = true;
            return;
        }
    }
    
    list[idx].isDeleted = true;
}

bool cmp(STRUCTURE a, STRUCTURE b) {
    if(a.y <= b.y) {
        if(a.y == b.y) {
            if(a.x >= b.x) {
                if(a.x == b.x) {
                    if(a.type < b.type) {
                        return true;
                    }
                    return false;
                }
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    N = n;
    vector<vector<int>> answer;
    
    for(int i = 0; i < build_frame.size(); i++) {
        int x = n - build_frame[i][1];
        int y = build_frame[i][0];
        int type = build_frame[i][2];
        int deploy = build_frame[i][3];
        
        // 설치일 때
        if(deploy == 1) {
            // 기둥
            if(type == 0 && checkDeployPillar(x, y)) {
                list.push_back({x, y, type, false});
                Pillar[x][y] = true;
            }
            // 보
            if(type == 1 && checkDeployBeam(x, y)) {
                list.push_back({x, y, type, false});
                Beam[x][y] = true;
            }
        }
        // 제거일 때
        else {
            // 기둥
            if(type == 0) {
                DeletePillar(x, y);
            }
            // 보
            if(type == 1) {
                DeleteBeam(x, y);
            }
        }
    }
    
    sort(list.begin(), list.end(), cmp);
    
    for(int i = 0; i < list.size(); i++) {
        if(list[i].isDeleted)
            continue;
        
        answer.push_back({list[i].y, N - list[i].x, list[i].type});
    }
    
    return answer;
}