programmers [C++] : 2020 KAKAO BLIND RECRUITMENT 기둥과 보 설치

www.programmers.co.kr/learn/courses/30/lessons/60061

프로그래머스

문제 설명

---

프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.

 

RULE

- 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.

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

 

2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1 x 1 크기입니다. 맨 처음 벽면은 비어있는 상태입니다. 기둥과 보는 격자선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있습니다.

TESTCASE #1 그림 예시

만약 (4, 2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3, 2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않습니다. 기둥과 보를 삭제하는 기능도 있는데 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.

 

 

접근 방법

---

삭제하고 추가할때마다 조건을 어긋나는지 아닌지를 판단하여 빌드 프레임을 완성한다. 

자세한 내용은 주석을 통해 설명해놓았습니다.

 

 

코드

---

#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
int col[102][102];
int bo[102][102];
int frame[102][102];

bool isBuilt(int x,int y, int type){
    if(type==0){
        if(y==0 || (y>=1&&col[y-1][x]==1) || bo[y][x]==1 || (x>=1&&bo[y][x-1]==1)) return true;
        else return false;
    }
    else if(type==1){
        if((y>=1&&(col[y-1][x]==1||col[y-1][x+1]==1)) || (x>=1&&bo[y][x-1]==1&&bo[y][x+1]==1)) return true;
        else return false;
    }
   
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    memset(col,0,sizeof(col));
    memset(bo,0,sizeof(bo));
    memset(frame,0,sizeof(frame));
    
    for(int i=0;i<build_frame.size();i++){
        int x= build_frame[i][0];
        int y= build_frame[i][1];
        int isCol= build_frame[i][2];
        int isBuild= build_frame[i][3];
        //설치
        if(isBuild==1){
            //기둥
            if(isCol==0){
                if(isBuilt(x,y,isCol)) {
                   frame[y][x]+=1;
                    col[y][x]=1;
                }
            }
            else if(isCol==1){
                if(isBuilt(x,y,isCol)){
                    frame[y][x]+=2;
                    bo[y][x]=1;
                }
            }
        }
        //삭제
        else if(isBuild == 0){
            //기둥
            if(isCol==0){
                //기둥을 삭제했다고 가정
                col[y][x]=0;
                //기둥을 삭제했는데, 위에 기둥이 존재하며 위의 기둥의 존재가 불가능할때
                // 다시 기둥을 냅두고 삭제를 못하니까 그냥 작업을 무시한다.
                if(col[y+1][x]==1 && !isBuilt(x,y+1,0)) col[y][x] = 1;
                // 위에 왼쪽으로 뻗은 보가 있고 이 보가 존재할 수 없다면,
                else if(x>=1 && bo[y+1][x-1]==1 && !isBuilt(x-1,y+1,1)) col[y][x] = 1;
                // 위에 오른쪽으로 뻗은 보가 있는 경우
                else if(bo[y+1][x]== 1 && !isBuilt(x,y+1,1)) col[y][x] = 1;
                // 위의 케이스에 해당되지 않으면 지울 수 있다. 기둥이므로 -1 해주자.
                else frame[y][x] -= 1;
            }
            // 삭제하고자 하는 오브젝트가 보일 경우
            else if(isCol== 1){
                // 역시 일단 보를 지울 수 있다고 가정하자
                bo[y][x]=0;
                // 왼쪽 모서리 위에 기둥이 있을 경우
                if(col[y][x] == 1 && !isBuilt(x, y, 0)) bo[y][x] = 1;
                // 오른쪽 모서리에 기둥이 있을 경우
                else if(col[y][x + 1] == 1 && !isBuilt(x + 1, y, 0)) bo[y][x] = 1;
                // 왼쪽에 보가 있을 경우
                else if(x >= 1 && bo[y][x - 1] == 1 && !isBuilt(x - 1, y, 1)) bo[y][x] = 1;
                // 오른쪽에 보가 있을 경우
                else if(bo[y][x + 1] == 1 && !isBuilt(x + 1, y, 1)) bo[y][x] = 1;
                // 해당하지 않으면 삭제. 보이므로 -2 해주자.
                else frame[y][x] -= 2;
            }
        }
    }
    for(int y = 0; y <= n; y++){
        for(int x = 0; x <= n; x++){
            //frame 0이 아닌, 즉 보든 기둥이든 뭐가 존재할 경우
            if(frame[y][x] != 0){
                // 기둥만 있을 경우 현재 answer의 현재 좌표에 (x, y, 0)을 넣어주자
                if(frame[y][x] == 1) answer.push_back({x,y,0});
                // 보만 있을 경우 현재 answer의 현재 좌표에 (x, y, 1)을 넣어주자
                else if(frame[y][x] == 2) answer.push_back({x,y,1});
                // 기둥, 보 둘 다 있을 경우 현재 answer의 현재 좌표에 (x, y, 0)와 (x, y, 1)을 넣어주자
                else if(frame[y][x] == 3){
                    answer.push_back({x,y,0});
                    answer.push_back({x,y,1});
                }
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}

funny algorithm 0_<