[Algorithm] 프로그래머스 '2020 KAKAO BLIND RECRUITMENT' C++ : 기둥과 보 설치

 

https://programmers.co.kr/learn/courses/30/lessons/60061

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

 

자! 다시한번 삽질한 것 = n이 작으면 그냥 다 돌려도 시간 얼마 안걸린다는 것~~~~

 

설치할 때는 그냥 주어진 조건에 부합하는지만 보면 되는데

 

삭제할 때는 일단 삭제 해보고 전체 요소들에 대해 부합하는지를 보면 됨

 

일단 삭제하고 체크한다까지는 맞았는데 전체 요소를 안보고 필요한 부분만 보려고 해서 괜히 삽질

 

그냥 board를 다 체크하니까 성공

 

문제만 길었지(공포감만 주고..) 그냥 돌리면 됨

 

 

 

 

Code

#include <string>
#include <vector>
#include <iostream>

using namespace std;

// 기둥 체크
bool check_gi(vector<vector<int>> board, int x, int y) {
    // 바닥
    if(y == 0) return true;
    
    // 보의 한쪽 끝 위 1
    if(board[x][y]==2 || board[x][y]==1) 
        return true;
    
    // 보의 한쪽 끝 위 2
    if(x-1>=0) {
        if(board[x-1][y]==2 || board[x-1][y]==1) 
            return true;
    }
    
    // 다른 기둥 위
    if(y-1>=0) {
        if(board[x][y-1]==2 || board[x][y-1]==0) 
            return true;
    }
        
    return false;
}

// 보 체크
bool check_bo(vector<vector<int>> board, int x, int y) {
    if(y-1>=0) {
        // 왼쪽 끝이 기둥 위
        if(board[x][y-1]==2 || board[x][y-1]==0) 
            return true;
        
        // 오른쪽 끝이 기둥 위
        if(x+1<board.size()) {
            if(board[x+1][y-1]==2 || board[x+1][y-1]==0) 
                return true;
        }
    }
    
    // 양쪽 끝이 보와 연결
    if(x-1>=0) {
        // 왼쪽
        if(board[x-1][y]==2 || board[x-1][y]==1) {
            // 오른쪽
            if(x+1<board.size()) {
                if(board[x+1][y]==2 || board[x+1][y]==1)
                    return true;
            }
        }
    }
    return false;
}

// 전체 board 체크
bool check_all(vector<vector<int>> board) {
    
    for(int i=0; i<board.size(); i++) {
        for(int j=0; j<board.size(); j++) {
            if(board[i][j] == 2) {
                if(!check_bo(board, i, j)) return false;
                if(!check_gi(board, i, j)) return false;
            }
            
            else if(board[i][j] == 1) {
                if(!check_bo(board, i, j)) return false;
            }
            
            else if(board[i][j] == 0) {
                if(!check_gi(board, i, j)) return false;
            }
        }
    }
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    vector<vector<int>> board(n+1, vector<int>(n+1, -1));
    
    // 명령어 돌기
    for(int i=0; i<build_frame.size(); i++) {
        int x = build_frame[i][0], y = build_frame[i][1];
        int type = build_frame[i][2], cmd = build_frame[i][3];
        
        // 설치
        if(cmd == 1) {
            // 기둥이면
            if(type == 0) {
                // 설치 가능한지 체크
                if(check_gi(board, x, y)) {
                    if(board[x][y] != -1) board[x][y] = 2; // 기둥+보
                    else board[x][y] = 0; // 온리 기둥
                }
            }
            // 보이면
            else {
                // 설치 가능한지 체크
                if(check_bo(board, x, y)) {
                    if(board[x][y] != -1) board[x][y] = 2; // 기둥+보
                    else board[x][y] = 1; // 온리 보
                }
            }
        }
        
        // 삭제
        else {
            int tmp = board[x][y]; // 되돌릴 수
            
            // 일단 삭제
            // 기둥이면
            if(type == 0) {
                if(tmp == 2) board[x][y] = 1; // 둘다 있는데 기둥만 삭제
                else if(tmp == 0) board[x][y] = -1; // 기둥만 있는데 기둥만 삭제
            }
            // 보이면
            else {
                if(tmp == 2) board[x][y] = 0; // 둘다 있는데 보만 삭제
                else if(tmp == 1) board[x][y] = -1; // 보만 있는데 보만 삭제
            }
            
            // 삭제 후 조건에 안맞으면
            if(!check_all(board)) {
                board[x][y] = tmp;
            }
        }
    }
    
    // board 읽기
    for(int i=0; i<board.size(); i++) {
        for(int j=0; j<board.size(); j++) {
            vector<int> v1, v2;
            int tmp = board[i][j];
            
            if(tmp == 2) {
                v1.push_back(i);
                v1.push_back(j);
                v1.push_back(0);
                answer.push_back(v1);
                
                v2.push_back(i);
                v2.push_back(j);
                v2.push_back(1);
                answer.push_back(v2);
            } 
            else if(tmp == 0 || tmp == 1) {
                v1.push_back(i);
                v1.push_back(j);
                v1.push_back(tmp);
                answer.push_back(v1);
            }
        }
    }
    
    return answer;
}