[C++] 2020 카카오 블라인드 기둥과 보 설치

접근 방법

---

 시뮬레이션 문제 입니다. 다만 문제를 조금 쉽게 풀기 위해서 생각해야 될 부분은

기둥과 보를 각각 2차원 배열로 따로 관리한다는 점과 삭제 연산 시에 현재 구조물을 삭제했을 때 영향을 받을 수 있는 주변의 구조물들이 온전하게 있을지에 대한 것입니다. 

 

시뮬레이션 과정은 총 4가지를 고려해야 합니다.

1. 기둥 설치, 2. 보 설치, 3. 기둥 삭제, 4. 보 삭제

 

기둥 배열을 bool col[][], 보 배열을 bool bo[][]라 한다면 

 

1의 경우

기둥이 바닥에 있거나 (y == 0)

보의 한쪽 끝 부분위에 있거나 (bo[y][x] == true || bo[y][x - 1] == true)

다른 기둥위에 있어야합니다. (col[y - 1][x] == true)

bool canBuildCol(int x, int y){
    return (y == 0 || col[y - 1][x] || bo[y][x] || bo[y][x - 1]);
}

 

2의 경우 

보는 한쪽 끝 부분이 기둥위에 있거나 (col[y - 1][x] || col[y - 1][x + 1])

양쪽 끝이 다른 보와 연결 되어 있어야 합니다. (bo[y][x - 1] && bo[y][x + 1])

bool canBuildBo(int x, int y){
    return (col[y - 1][x] || col[y - 1][x + 1] || (bo[y][x - 1] && bo[y][x + 1]));
}

 

3의 경우

기둥을 삭제하면 영향을 받을 수 있는 구조물은 3개가 있습니다.

빨간색 기둥을 삭제 한다면 2개의 파란색 보와, 윗 부분의 파란색 기둥이 영향을 받을 수 있는데 

 이러한 구조물이 없다면 삭제해도 되지만 구조물이 있다면 빨간색 구조물이 없을 때에도 온전하게 있을 수 있는지 검사를 해야합니다.

 

  (1) 기둥의 상단에 기둥이 있다면, 기둥을 삭제한 후 상단의 기둥이 온전히 있을 수 있는지

  (2) 기둥의 좌측 상단에 보가 있다면, 기둥을 삭제한 후 좌측 상단의 보가 온전히 있을 수 있는지

  (3) 기둥의 상단에 보가 있다면, 기둥을 삭제한 후 그 상단의 보가 온전히 있을 수 있는지 

  col[y][x] = false;
  if((col[y + 1][x] && !canBuildCol(x, y+1)) || 
  	(bo[y + 1][x] && !canBuildBo(x, y + 1)) || 
  	(bo[y + 1][x - 1] && !canBuildBo(x - 1, y + 1))){
  	
    col[y][x] = true;
  }

온전히 있을 수 없다면 다시 기둥을 설치합니다.

 

 

4의 경우 

보를 삭제하면 영향을 받을 수 있는 구조물은 4개가 있습니다. 

 빨간색 보를 삭제하게 된다면 양쪽 끝의 보 2개와 기둥 2개가 영향을 받습니다. 

위와 마찬가지로 4가지 구조물에 대한 검사를 합니다. 

 

  (1) 우측에 보가 있다면, 보를 삭제한 후 우측의 보가 온전히 있을 수 있는지 

  (2) 좌측에 보가 있다면, 보를 삭제한 후 좌측의 보가 온전히 있을 수 있는지 

  (3) 자신의 위치에 기둥이 있다면, 보를 삭제한 후 그 기둥이 온전히 있을 수 있는지 

  (4) 우측에 기둥이 있다면, 보를 삭제한 후 우측의 기둥이 온전히 있을 수 있는지 

bo[y][x] = false;
if((col[y][x] && !canBuildCol(x, y)) || 
	(col[y][x + 1] && !canBuildCol(x + 1, y)) || 
	(bo[y][x - 1] && ! canBuildBo(x - 1, y)) || 
	(bo[y][x + 1] && !canBuildBo(x + 1, y)) ){

	bo[y][x] = true;
}

온전히 있을 수 없다면 다시 보를 설치 합니다.

 

 

 마지막으로 정답을 출력하기 위한 정렬 순서로는 x좌표 순 오름차순, x좌표가 같다면 y좌표 순 오름차순, 둘 다 같다면 기둥이 먼저 출력이 되어야 합니다.

    for(int x=0;x<=n;x++){
        for(int y=0;y<=n;y++){
            if(col[y][x])
                answer.push_back({x,y,0});
            if(bo[y][x])
                answer.push_back({x,y,1});
        }    
    }
        

 

 

소스 코드

---

#include <string>
#include <string.h>
#include <vector>
#include <iostream>

using namespace std;

bool bo[101][101];
bool col[101][101];

bool canBuildCol(int x, int y){
    return (y == 0 || col[y - 1][x] || bo[y][x] || bo[y][x - 1]);
}

bool canBuildBo(int x, int y){
    return (col[y - 1][x] || col[y - 1][x + 1] || (bo[y][x - 1] && bo[y][x + 1]));
}

void solve(vector<int> &info){
    
    int x = info[0];
    int y = info[1];
    int type = info[2];
    int build = info[3];
    
    if(type == 0 && build == 1){
        if(canBuildCol(x, y))
            col[y][x] = true;
    }
    else if(type == 1 && build == 1){
        if(canBuildBo(x, y))
            bo[y][x] = true;
    }
    else if(type == 0 && build == 0){
        col[y][x] = false;
        if((col[y + 1][x] && !canBuildCol(x, y+1)) || 
           (bo[y + 1][x] && !canBuildBo(x, y + 1)) || 
           (bo[y + 1][x - 1] && !canBuildBo(x - 1, y + 1))){
            
            col[y][x] = true;
        }
    }
    else{
        bo[y][x] = false;
        if((col[y][x] && !canBuildCol(x, y)) || 
           (col[y][x + 1] && !canBuildCol(x + 1, y)) || 
           (bo[y][x - 1] && ! canBuildBo(x - 1, y)) || 
           (bo[y][x + 1] && !canBuildBo(x + 1, y)) ){
            
            bo[y][x] = true;
        }
    }
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    
    vector<vector<int>> answer;
    
    memset(bo, false, sizeof(bo));
    memset(col, false, sizeof(col));
    
    for(int i=0;i<build_frame.size();i++)
        solve(build_frame[i]);
    
    for(int x=0;x<=n;x++){
        for(int y=0;y<=n;y++){
            if(col[y][x])
                answer.push_back({x,y,0});
            if(bo[y][x])
                answer.push_back({x,y,1});
        }    
    }
        
    return answer;
}