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

풀이)

한가지 조건을 간과해서 오래 걸렸던 문제이다.

조건

같은 좌표상에 기둥과 보가 둘 다 있을 수 있다. -> 따라서 좌표상에 있는 구조물을 표시하기 위해 삼중 배열 사용했다.

int  visited[102][102][2];

 // visited[x][y][0] : (x,y)좌표일때 기둥이 지어진지 여부, visited[x][y][1] : (x,y)좌표일 때 보가 지어진지 여부

 // visited[x][y][0] = 1 : (x,y)좌표에 기둥이 지어져 있다 라는 뜻이다.

설치 조건은 주어진 조건을 생각하여 작성했으나, 제거할때의 조건은 일일히 구현하기가 까다로웠다.

그래서 그냥 제거를 먼저 해본 뒤 나머지 구조물들이 설치 조건을 만족하는 지 일일히 확인해보았다.

기둥이나 보 제거 -> 나머지 구조물 확인 -> 나머지들이 만족하면 제거 확정, 만족못하면 제거 명령 무시

모든 작업을 마치고는, 모든 좌표를 다 둘러봐 최종 구조물의 상태를 return해줬다.

코드)

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

int size;
int visited[102][102][2];//x,y좌표, 세어진 것표시

bool check_gi(int x,int y){ //기둥이 만들어질 수 있는지 확인하는 함수
    if(y==0) return true; // 바닥에 있거나
    if(x-1 >=0 && visited[x-1][y][1])return true;//보의 한쪽끝에있거나
    if(x+1< size && visited[x][y][1]) return true;
    if(y-1>=0 && visited[x][y-1][0]) return true;//또다른 기둥위에 있으면

    return false;
}
bool check_bo(int x,int y){//보가 만들어질수 있는지 확인
    //한쪽끝이 기둥위에있거나
    if(y-1 >=0){
        if(visited[x+1][y-1][0]|| visited[x][y-1][0]) return true;
    }
    //양쪽이 다른 보와 동시에 연결되어있거나
    if(x-1 >=0 && x +1 <=size && visited[x-1][y][1] && visited[x+1][y][1]){
        return true;
    }
    return false;
}

bool destruct(){
     for(int i = 0 ; i <= size ; ++i){
        for(int j = 0 ; j <= size ; ++j){
            if(visited[i][j][0] && !check_gi(i, j)){
                return false;
            }
            if(visited[i][j][1] && !check_bo(i, j)){
                return false;
            }
        }
    } 
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {

    vector<vector<int>> answer;
   for(int i=0;i<=n;i++){
       for(int j=0;j<=n;j++){
           for(int k=0;k<2;k++){
               visited[i][j][k] = 0;
           }
       }
   }
    //입력 x,y,a(0은기둥 1은보),b(0은 삭제 1은 설치)
    int x,y,a,b;
    size = n;
    //cout << size << endl;
    for(int i=0;i<build_frame.size();i++){
        x = build_frame[i][0];
        y = build_frame[i][1];
        a = build_frame[i][2];
        b = build_frame[i][3];
        //cout << x << y <<a<< b << endl;
        if(b==0){ // 제거
            if(a==0){
                visited[x][y][0] = 0;
                if(destruct()){
                    continue;
                }
                visited[x][y][0] =1;
            }
            else{
                visited[x][y][1] = 0;
                if(destruct()){
                    continue;
                }
                visited[x][y][1] =1;
            }
        }
        else{//설치
            if(a==0){//기둥
                if(check_gi(x,y)){ //기둥을 지을수 있는 곳인지 확인
                    visited[x][y][0] = 1;
                }
            }
            else{
               if(check_bo(x,y)){
                   visited[x][y][1] =1;
               }
            }  
        }
    }
    vector <int> temp(3);
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            temp[0] = i;
            temp[1] = j; 
            if(visited[i][j][0]){
                temp[2] = 0;
                answer.push_back(temp);
            }
            if(visited[i][j][1]){
                temp[2] = 1;
                answer.push_back(temp);
            }
        }
    }
    return answer;
}