[프로그래머스/Level 3] 기둥과 보 설치 (C++)

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

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

카카오 기출

어려운 구현 문제였습니다. 문제 해결의 아이디어는 기둥과 보가 존재하는지 각각 2차원 배열을 통해 나타내는 것입니다. 이때 문제에서는 (0, 0)이 맨 왼쪽 아래부터 시작햔다는 점입니다. 배열에서는 맨 오른쪽 위 부터 시작하는데, 이는 다음과 같이 시계방향으로 90도 회전했다고 생각하면 되므로, 배열로 충분히 해결할 수 있습니다.

 

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

그리고 무엇보다 기둥 혹은 보를 삭제할 수 있는지 확인하는 조건을 구현하는 것이 많이 어려운 문제였습니다. 현재 좌표를 기준으로 기둥 또는 보를 미리 삭제 처리하고, 3x2의 크기만큼만 탐색하면서 기둥이나 보를 만났을 때, 이게 설치가 가능한건지 확인함으로써 가능하면 그대로 false 처리, 설치가 불가능하다면 false 처리했던 것을 다시 true처리 해줬습니다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool pillar[102][102], beam[102][102];

// 기둥을 설치할 수 있는지 확인
bool checkPillar(int x, int y) {
    if(y == 0 || pillar[x][y - 1]) return true;
    if(beam[x][y] || (x > 0 && beam[x - 1][y])) return true;
    return false;
}

// 보를 설치할 수 있는지 확인
bool checkBeam(int x, int y) {
    if((y > 0 && pillar[x][y - 1]) || (y > 0 && pillar[x + 1][y - 1])) return true;
    if((x > 0 && beam[x - 1][y]) && beam[x + 1][y]) return true;
    return false;
}

// 기둥 혹은 보를 삭제할 수 있는지 확인
bool canDelete(int x, int y) {
    for(int i = max(0, x - 1); i <= x + 1; i++) {
        for(int j = y; j <= y + 1; j++) {
            if(pillar[i][j] && !checkPillar(i, j)) return false;
            if(beam[i][j] && !checkBeam(i, j)) return false;
        }
    }
    
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    
    for(auto b : build_frame) {
        int x = b[0]; // 가로
        int y = b[1]; // 세로
        int type = b[2]; // 기둥 or 보
        int action = b[3]; // 설치 or 삭제
        
        if(type == 0) {
            if(action == 1 && checkPillar(x, y)) pillar[x][y] = true;
            else {
                pillar[x][y] = false;
                if(!canDelete(x, y)) pillar[x][y] = true;
            }
        } else {
            if(action == 1 && checkBeam(x, y)) beam[x][y] = true;
            else {
                beam[x][y] = false;
                if(!canDelete(x, y)) beam[x][y] = true;
            }
        }
    }
    
    // '보' 보다 '기둥'이 먼저 설치되야 하므로, 기둥부터 넣는다.
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            if(pillar[i][j]) answer.push_back({i, j, 0});
            if(beam[i][j]) answer.push_back({i, j, 1});
        }
    }
    
    return answer;
}