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

문제 링크

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

프로그래머스

최대 1000개의 건설 명령을 처리한 후 최종적으로 남아있는 기둥과 보의 위치를 리턴하자.

 

풀이

명령 형식은 {x좌표, y좌표, 기둥 or 보, 삭제 or 설치}로 구성된 벡터 형식이다.

이때 기둥과 보가 설치될 수 있는 조건이 있다.

● 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
● 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

위의 두 조건을 만족하지 못하면, 삭제 혹은 설치를 할 수 없다.

위의 조건을 어기는 명령이 들어올 경우는 명령을 무시한다.

 

처음에 나는 엄청난 경우의 예외들을 처리해야 하는 단순 구현 문제라고 생각했다. 설치 또는 제거 명령이 들어왔을 때 발생할 수 있는 예외 상황을 하나 하나 예상하면서 최대한 구현을 했다.

예제 문제는 다 맞혔지만, 처리를 못한 예외가 있었는 지 정확성 테스트 대부분에서 실패가 나왔다.

 

우리가 가장 쉽게 생각할 수 있는 방법 중 하나는 설치 또는 삭제를 한 후에 모든 기둥이나 보가 조건을 만족하는 지 확인하는 방법이다.

하지만 이 방법을 처음에 시도하지 않았던 이유는 시간이 너무 오래 걸릴 것 같아서 시도조차 하지 않았다.

그런데 명령은 최대 1000개로 입력이 그렇게 많지 않다. 계속해서 건물을 설치하는 명령만 들어온다고 해도 그리 많은 탐색이 필요하지 않음을 짐작할 수 있다.

 

설치된 건물의 정보는 building이라는 벡터 집합에 저장해두었다. set<vector<int>> building

벡터가 아닌 set에 정보를 저장하는 이유는 탐색과 삭제가 간단하기 때문이다.

또한 정답도 오름차순으로 정렬해서 리턴해야 하는데, set은 알아서 정렬을 시켜주기 때문에 따로 정렬해 줄 필요가 없다.

 

1. 기둥이 서있을 수 있는 조건

기둥이 x, y에 설치되어있다고 하자. 

제시된 조건에 의해 y == 0 이거나, (x, y-1)에 설치된 기둥이 존재하거나, (x, y-1) 또는 (x-1, y-1)에 보가 존재하면 된다.

=> 바닥이거나, 아래에 기둥 또는 보가 존재하면 된다.

위의 4가지 조건 중 하나라도 만족하면 해당 기둥은 조건을 만족시킨다.

반대로 4가지 조건을 모두 만족하지 못한다면 해당 기둥은 설치될 수 없다.

 

2. 보가 설치될 수 있는 조건

보가 x, y에 설치되어있다고 하자.

제시된 조건에 의해  (x, y - 1) 또는 (x+1, y - 1)에 기둥이 존재하거나, (x-1, y)와 (x+1, y) 모두에 보가 존재하면 된다.

=> 아래에 기둥이 하나라도 존재하거나, 양쪽에 보가 설치되어 있으면 된다.

위의 3가지 조건 중 하나라도 만족하면 해당 보는 조건을 만족시킨다.

반대로 3가지 조건을 모두 만족하지 못하면 해당 보는 설치될 수 없다.

 

명령을 일단 수행한 후 위의 과정을 통해 모든 기둥과 보가 조건을 만족시키는 지 확인한다.

하나라도 만족하지 않는 기둥 또는 보가 있다면 해당 명령을 철회한다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100 + 5;
set<vector<int>> building;
 
bool is_ok(){
    for(auto build : building){
        if(!build[2]){//기둥
            int x = build[0];
            int y = build[1];
            if(y == 0)
                continue;
            vector<int> necessary[3] = {{x,y-1, 0}, {x-1,y,1}, {x,y,1}};
            bool chk = false;
            for(int i = 0; i< 3; i++){
                if(building.find(necessary[i]) != building.end()){
                    chk = true;
                    break;
                }
            }
            if(chk)
                continue;
            return false;
        }
        else if(build[2]){//보
            int x = build[0];
            int y = build[1];
            vector<int> necessary[4] = {{x,y-1, 0}, {x+1, y-1, 0}, {x-1, y ,1} , {x+1,y,1}};
            if(building.find(necessary[0]) != building.end())
                continue;
            else if(building.find(necessary[1]) != building.end())
                continue;
            else if(building.find(necessary[2]) != building.end()
                   && building.find(necessary[3]) != building.end())
                continue;
            return false;
        }
    }
    return true;
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    for(auto build : build_frame){
        vector<int> v = {build[0], build[1], build[2]};
        int how = build[3];
        
        if(!how){ //삭제
            building.erase(v);
            if(is_ok()) continue;
            else building.insert(v);
        }
        else if(how){ //설치
            building.insert(v);
            if(is_ok()) continue;
            else building.erase(v);
        }
    }
    
    for(auto v : building)
        answer.push_back(v);   
    return answer;
}