[c++][프로그래머스] 기둥과 보 설치

프로그래머스 기둥과 보 설치 [2020 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/60061

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

문제 풀이

• 이 문제는 구현 문제입니다. 따로 알고리즘을 사용하는 것이 아니니 문제의 요구사항에 따라 침착하게 구현해주시면 됩니다. 
• 문제의 요구사항은 다음과 같습니다.
  • 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
  • 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
  • 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.
• 설치 로직은 요구사항에 따라 조건문으로 구현하시면 되고, 삭제 로직은 현재 삭제하려는 것을 삭제해도 다른 것들이 정상적으로 설치될 수 있는가의 관점에서 접근하시면 됩니다. 예를 들어 기둥을 삭제하려고 할 때, 기둥 위에 다른 기둥이 있다면 현재 이 기둥을 삭제해도 위의 기둥이 설치될 수 있는가의 접근입니다. 코드로 보시면 조금 더 쉽게 이해하실 수 있을 것 같습니다.

코드

#include <vector>
#include <algorithm>

using namespace std;

int arr[101][101][2];
int N;

bool install_item(int x, int y, int a) {
    if(a == 0) { // 기둥 설치
        if(y == 0) return true; // 바닥위에 있거나
        if(x > 0 && arr[x-1][y][1]) return true; // 보의 오른쪽 끝 위
        if(y < N && arr[x][y][1]) return true; // 보의 왼쪽 끝 위
        if(y > 0 && arr[x][y-1][0]) return true; // 다른 기둥 위
    }
    else { // 보 설치
        if(y > 0 && arr[x][y-1][0]) return true; // 왼쪽 끝 아래 기둥
        if(x < N && y > 0 && arr[x+1][y-1][0]) return true; // 오른쪽 끝 아래 기둥
        if(x > 0 && x < N && arr[x-1][y][1] && arr[x+1][y][1]) return true; // 양쪽 끝 부분 다른 보
    }
    return false;
}

bool remove_item(int x, int y, int a) {
    arr[x][y][a] = 0;
    
    if(a == 0) { // 기둥 삭제
        // 위에 기둥 있을 때, 설치 가능?
        if(y < N && arr[x][y+1][0] && !install_item(x, y+1, 0)) return false;
        
        // 위에 보 있을 때, 설치 가능?
        if(y < N && arr[x][y+1][1] && !install_item(x, y+1, 1)) return false;
        if(x > 0 && y < N && arr[x-1][y+1][1] && !install_item(x-1, y+1, 1)) return false;
    }
    else {
        // 위에 기둥 있을 때, 설치 가능?
        if(arr[x][y][0] && !install_item(x, y, 0)) return false;
        if(x < N && arr[x+1][y][0] && !install_item(x+1, y, 0)) return false;
        
        // 다른 보와 연결되어 있을 때, 설치 가능?
        if(x > 0 && arr[x-1][y][1] && !install_item(x-1, y, 1)) return false;
        if(x < N && arr[x+1][y][1] && !install_item(x+1, y, 1)) return false;
    }
    
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    N = n;
    vector<vector<int>> answer;
    
    for(auto frame: build_frame) {
        int x = frame[0];
        int y = frame[1];
        int a = frame[2];
        int b = frame[3];
        
        if(b == 0) {
            if(!remove_item(x, y, a)) arr[x][y][a] = 1;
        }
        else {
            if(install_item(x, y, a)) arr[x][y][a] = 1;
        }
    }
    
    for(int i=0; i<=n; ++i) {
        for(int j=0; j<=n; ++j) {
            if(arr[i][j][0]) answer.push_back({i, j, 0});
            if(arr[i][j][1]) answer.push_back({i, j, 1});
        }
    }
    
    return answer;
}

 

실행 결과