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

문제

기둥과 보 설치

풀이

문제에 주어진 조건대로 구현하는 문제인데 쉽지 않다... 🥲

풀이에 앞서 내가 처음에 잘못 생각한 부분은 다음과 같다. 구조물이 겹치도록 설치하는 경우는 주어지지 않는다.라는 조건이 하나의 좌표 (x, y)에 기둥과 보 둘 다 설치할 수 없다는 뜻인 줄 알았다.. 하지만 리턴 조건에서 x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 됩니다.라고 주어진 것으로 보아 같은 좌표에 설치 가능한 것을 확인할 수 있다. (즉 보의 왼쪽 위에도 기둥 설치가 가능하다.)

그래서 기둥과 보 설치 여부를 체크하는 이차원 벡터를 따로 두었다.
기둥은 zero, 보는 one에 체크한다.

기둥 설치가 가능한 경우

• 바닥 위
• 보의 왼쪽 위
• 보의 오른쪽 위
• 기둥 위

보 설치가 가능한 경우

• 기둥의 오른쪽 위
• 기둥의 왼쪽 위
• 왼쪽에 보, 오른쪽에 보가 있어 양쪽 보 가운데

삭제
기둥이나 보를 삭제할 때는 구조물을 삭제 했다고 가정하고, 삭제한 구조물 주변에 있는 구조물들이 다시 설치할 수 있는지를 확인한다.

기둥 또는 보를 삭제할 때 조건을 나눠서 따지는 방법도 있지만 n이 100이하라서 (x,y)를 기준으로 9칸 모두 체크해도 시간 초과가 뜨지 않는다.

소스코드

#include <string>
#include <vector>

using namespace std;

vector<vector<bool>> zero; // 기둥
vector<vector<bool>> one; // 보
int num;

bool isValid(int x, int y, int a) {
    if (a == 0) { // 기둥 설치
        if (y == 0) return true; // 바닥
        if (x > 0 && one[x - 1][y]) return true; // 보 오른쪽 위
        if (one[x][y]) return true; // 보 왼쪽 위
        if (zero[x][y - 1]) return true; // 기둥 위
    } else { // 보 설치
        if (y > 0 && zero[x][y - 1]) return true; // 기둥 위 오른쪽
        if (x < num && y > 0 && zero[x + 1][y - 1]) return true; // 기둥 위 왼쪽
        if ((x > 0 && one[x - 1][y]) && (x < num && one[x + 1][y])) return true; // 양쪽 보 가운데
    }
    return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    zero.assign(n + 1, vector<bool>(n + 1, false));
    one.assign(n + 1, vector<bool>(n + 1, false));
    num = n;
    for (auto i: build_frame) {
        int x = i[0];
        int y = i[1];
        int a = i[2];
        int b = i[3];
        if (b == 1) { // 설치하기
            if (a == 0) {
                if (isValid(x, y, a)) zero[x][y] = true;
            } else {
                if (isValid(x, y, a)) one[x][y] = true;
            }
        } else { // 삭제하기
            if (a == 0) { // 기둥 삭제
                zero[x][y] = false;
                bool flag = true;
                for (int dx = -1; dx <= 1; dx++) {
                    for (int dy = -1; dy <= 1; dy++) {
                        flag = true;
                        int nx = x + dx;
                        int ny = y + dy;
                        if (nx < 0 || ny < 0 || nx > num || ny > num) continue;
                        if (zero[nx][ny]) {
                            flag = isValid(nx, ny, 0);
                            if (!flag) break;
                        }
                        if (one[nx][ny]) {
                            flag = isValid(nx, ny, 1);
                            if (!flag) break;
                        }
                    }
                    if (!flag) break;
                }
                if (!flag) {
                    zero[x][y] = true;
                }
            } else { // 보 삭제
                one[x][y] = false;
                bool flag = true;
                for (int dx = -1; dx <= 1; dx++) {
                    for (int dy = -1; dy <= 1; dy++) {
                        flag = true;
                        int nx = x + dx;
                        int ny = y + dy;
                        if (nx < 0 || ny < 0 || nx > num || ny > num) continue;
                        if (zero[nx][ny]) {
                            flag = isValid(nx, ny, 0);
                            if (!flag) break;
                        }
                        if (one[nx][ny]) {
                            flag = isValid(nx, ny, 1);
                            if (!flag) break;
                        }
                    }
                    if (!flag) break;
                }
                if (!flag) {
                    one[x][y] = true;
                }
            }
        }
    }

    for (int i = 0; i <= num; i++) {
        for (int j = 0; j <= num; j++) {
            if (zero[i][j]) {
                vector<int> tmp(3);
                tmp[0] = i;
                tmp[1] = j;
                tmp[2] = 0;
                answer.push_back(tmp);
            }
            if (one[i][j]) {
                vector<int> tmp(3);
                tmp[0] = i;
                tmp[1] = j;
                tmp[2] = 1;
                answer.push_back(tmp);
            }
        }
    }

    return answer;
}