[프로그래머스, C++] 기둥과 보 설치(2020 카카오 블라인드 채용)

문제 링크

코딩테스트 연습 - 기둥과 보 설치

 

 

 

풀이

진짜 비교구문 누가 더 빨리 짜나 문제였던거 같다.(시간 싸움)

이 문제에서 주의할 점은 row, column이 x,y와 반대라는 점이 중요하다.(출력할 때 다르다)

하지만 그대로 (x, y)라고 생각하고 풀어도 기준(pivot)이 같으므로 답은 일치한다.

문제를 풀고 다른 풀이를 봐도 기본 c++은 100줄은 이상인 듯하다.

 

// 요약

board: (n+1) x (n+1)

board[i][j] 값이 0이면 기둥, 1이면 보, 2이면 기둥+보, -1이면 nothing을 뜻한다.

gidoong(): 기둥이 이 자리에 있어도 되는 지 판별 함수(인자로 x,y를 받음)

bo(): 보가 이 자리에 있어도 되는 지 판별 함수(인자로 x,y를 받음)

check(): 기둥과 보가 모두 기준에 맞춰서 있는 지의 판별 함수

solution(): 문제 풀이

1) build_frame의 원소를 돌면서 board에 할당한다.

2) check() 함수로 맞는지 판별

3) true면 그대로 continue, faluse면 backup해놓은 것과 swap()한다.(backup은 앞에서 미리 복사생성자를 통해 만든다)

4) answer에 할당해준다.(기준에 있는 정렬이 그대로 기둥, 보로 push_back()해준다.)

 

 

#include <string>
#include <vector>

using namespace std;

// 기둥은 1.바닥 위, 2.보의 한쪽 끝 부분 위, 3.다른 기둥 위
// 보는 1.한쪽 끝 부분이 기둥 위, 2.양쪽 끝 부분이 다른 보와 동시 연결

// [x, y, a, b]
// (x, y) = (가로, 세로)
// a가 0 = 기둥, 1 = 보
// b가 0 = 삭제, 1 = 설치

// return 배열은 x좌표 기준 오름차순 정렬, x좌표 같을 경우 y좌표 기준 오름차순
// x, y 모두 같을 경우 기둥 먼저, 보 나중

bool gidoong(vector<vector<int>>& board, int x, int y){     // 기둥이 될 조건
    if(y == 0) return true;     // 바닥 위
    if(board[x][y-1]==0 || board[x][y-1]==2) return true;      // 기둥 위
    if(board[x][y]==1 || board[x][y]==2) return true;       // 보 왼쪽 위
    if(x>0 && (board[x-1][y]==1 || board[x-1][y]==2)) return true; // 보 오른쪽 위
    return false;
}

bool bo(vector<vector<int>>& board, int x, int y){          // 보가 될 조건
    if(board[x][y-1]==0 || board[x][y-1]==2) return true;       // 왼쪽에 기둥 위
    if(board[x+1][y-1]==0 || board[x+1][y-1]==2) return true;   // 오른쪽에 기둥 위
    if(x>0 && x<board.size()-1 && 
       (board[x-1][y]==1 || board[x-1][y]==2) && (board[x+1][y]==1 || board[x+1][y]==2))
        return true;

    return false;
}

bool check(vector<vector<int>>& board){
    for(int i=0; i<board.size(); i++){
        for(int j=0; j<board[i].size(); j++){
            if(board[i][j] != -1){
                switch(board[i][j]){
                    case 0: if(!gidoong(board, i, j)) return false;     // 기둥
                        break;
                    case 1: if(!bo(board, i, j)) return false;      // 보
                        break;
                    case 2: if(!gidoong(board, i, j) || !bo(board, i, j))return false;  // 기둥+보
                        break;
                }
            }
        }
    }
    return true;
}

void print(vector<vector<int>>& board){
    for(int i=0; i<board.size(); i++){
        for(int j=0; j<board[i].size(); j++){
            if(board[i][j]!=-1)
                printf("%d, ", board[i][j]);
            else
                printf(" , ");
        }
        printf("\n");
    }
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    
    // 보드 생성
    vector<vector<int>> board(n+1);
    vector<int> minus(n+1, -1);
    for(int i=0; i<n+1; i++){
        board[i].insert(board[i].begin(), minus.begin(), minus.end());
    }
    
    // 처리
    for(int i=0; i<build_frame.size(); i++){
        vector<vector<int>> backup(board);
        // 삭제(false) or 설치(true) and 연산
        bool isSet = build_frame[i][3]==1 ? true:false;
        // 기둥(false) or 보(true)
        bool isBo = build_frame[i][2]==1 ? true:false;
        // 좌표
        int x = build_frame[i][0];
        int y = build_frame[i][1];
        if(isSet){
            // 설치
            if(isBo){
                switch(board[x][y]){
                    case -1: board[x][y] = 1;
                        break;
                    case 0: board[x][y] = 2;
                        break;
                }
            }
            else{
                switch(board[x][y]){
                    case -1: board[x][y] = 0;
                        break;
                    case 1: board[x][y] = 2;
                        break;
                }
            }
        }
        else{
            // 삭제
            if(board[x][y]!=-1){
                if(isBo){
                    // 보
                    switch(board[x][y]){
                    case 1: board[x][y] = -1;
                        break;
                    case 2: board[x][y] = 0;
                        break;
                    }
                }
                else{
                    // 기둥
                    switch(board[x][y]){
                    case 0: board[x][y] = -1;
                        break;
                    case 2: board[x][y] = 1;
                        break;
                    }
                }
            }
        }
        if(!check(board)) board.swap(backup);       // backup과 swap
    }
    
    // answer에 할당
    for(int i=0; i<n+1; i++){
        for(int j=0; j<n+1; j++){
            if(board[i][j]!=-1){
                vector<int> v;
                v.push_back(i);
                v.push_back(j);
                if(board[i][j]==2){
                    v.push_back(0);
                    answer.push_back(v);
                    v.pop_back();
                    v.push_back(1);
                    answer.push_back(v);
                }
                else if(board[i][j]==0 || board[i][j]==1){
                    v.push_back(board[i][j]);
                    answer.push_back(v);
                }
            }
        }
    }
    return answer;
}