2020 KAKAO BLIND RECRUITMENT : 기둥과 보(c++) / 구현

문제의 핵심은 

기둥과 보를 설치하는 것이 아니라 삭제하는 부분이라고 생각합니다.

설치를 할 때는 설치하는 부분만 확인을 하면 되지만, 삭제는 삭제를 한 후 다른 모든 기둥과 보가 규칙을 만족하는 지를 일일히 확인해주어야 합니다.

 

물론 삭제하는 기둥이나 보의 근처에 있는 기둥과 보만 검사를 하는 방법도 있겠지만?

너무 많다....ㅎㅎ 그래서 그냥 다 검사해보는 방법으로 코드를 구현했습니다.

 

그래서 삭제 부분은

1) 기둥이나 보를 일단 삭제한다.

3) 그리고 모든 기존에 있던 모든 기둥과 보를 검사하며 그 자리에 있던 기둥과 보를 삭제하고 다시 넣었을 때 규칙을 성립하는 지 확인해주었다. => 모두 규칙을 성립한다? 그럼 그냥 삭제 / 하나라도 규칙 성립 x? 그럼 그냥 넣는다.

 

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int wall[102][102][3] = {0, };
int N;
 
bool add(int x, int y, int a){
    if(a==0){ // 기둥
        // 바닥 위
        if(y==0){
            return true;
        }
        
        // 보의 한쪽 부분 위
        if((x-1>=0 && wall[x-1][y][1]==1) || wall[x][y][1]==1){
            return true;
        }
        
        // 다른 기둥 위
        if(y-1>=0 && wall[x][y-1][0]==1){
            return true;
        }
        
    }else{ // 보
        // 한쪽 끝 부분이 기둥 위
        if((y-1>=0 && wall[x][y-1][0]==1) || (wall[x+1][y-1][0]==1 && x+1<=N && y-1>=0)){
            return true;
        }
        
        // 양쪽 부분이 다른 보와 동시에 연결
        if((x-1>=0 && wall[x-1][y][1]==1) && (wall[x+1][y][1]==1 && x+1<=N)){
            return true;
        }
    }
    
    return false;
}
 
bool remove()
{
    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            for(int k=0; k<2; k++){
                if(wall[i][j][k]==1){
                    wall[i][j][k] = 0;
                    if(!add(i, j, k)){
                        wall[i][j][k] = 1;
                        return false;
                    }
                    wall[i][j][k] = 1;
                }
            }
        }
    }
    
    return true;
}
 
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    
    N = n;
    for(int i=0; i<build_frame.size(); i++){
        int x = build_frame[i][0];
        int y = build_frame[i][1];
        int a = build_frame[i][2];
        int b = build_frame[i][3];
 
        if(b==0){
            wall[x][y][a] = 0;
            if(!remove()){
                wall[x][y][a] = 1;
            }
        }else{
            if(add(x, y, a)){
                wall[x][y][a] = 1;
            }
        }
    }
    
    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            for(int k=0; k<2; k++){
                if(wall[i][j][k]==1){
                    vector<int> temp;
                    temp.push_back(i);
                    temp.push_back(j);
                    temp.push_back(k);
                    answer.push_back(temp);
                }
            }
        }
    }
    
    return answer;
}