[구현] (프로그래머스 Lv 3) 기둥과 보 설치

문제

• 문제 링크
• 문제 설명: 프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.
  • 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
  • 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
  • 기둥은 좌표 (x, y)에서 (x, y+1) 방향으로 놓여짐
  • 보는 좌표 (x, y)에서 (x+1, y) 방향으로 놓여짐
  • 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.

• 벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성해주세요.
• 입력
  • n은 5 이상 100 이하인 자연수
  • build_frame의 세로(행) 길이는 1 이상 1,000 이하
  • build_frame의 원소는 [x, y, a, b]형태
    • x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표 [가로 좌표, 세로 좌표]
    • a는 설치 또는 삭제할 구조물의 종류 (0은 기둥 1은 보)
    • b는 구조물을 설치할 지, 혹은 삭제할 지 (0은 삭제 1은 설치)
    • 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다.
    • 바닥에 보를 설치 하는 경우는 없습니다.
• 출력: 배열의 원소는 [가로 좌표, 세로 좌표, 구조물의 종류]로 오름차순된 형태

n	build_frame	result
5	[[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]]	[[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]
5	[[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]]	[[0,0,0],[0,1,1],[1,1,1],[2,1,1],[3,1,1],[4,0,0]]

풀이

• 문제에서 정해진 규칙이 유지되는지 검사하는 함수(check)와 배열에 기둥/보를 설치 및 삭제하는 작업을 하는 함수(build)를 작성
• 기둥과 보 2가지 구조물만 가지므로 비트 연산으로 해당 위치에 구조물의 존재를 파악
• 설치할 때는 설치 위치에 대해서만 조건을 검사하면 되지만, 삭제할 때는 삭제 후 주변 구조물에 대해 조건을 만족하는지 검사해야 하므로 check함수를 여러 번 호출해주어야 함
• 작업별 조건
  • 기둥 설치: 설치할 위치가 바닥/보 또는 왼쪽에 보 또는 아래에 기둥
  • 보 설치: 설치할 위치에 기둥 또는 오른쪽에 기둥 또는 양쪽에 보
  • 기둥 삭제: 삭제후 (x-1,y+1), (x,y+1) 위치에 있는 보/기둥에 대해 위의 조건들을 각각 검사
  • 보 삭제: 삭제후 (x-1,y), (x+1,y)에 있는 보 또는 (x,y), (x+1,y)에 있는 기둥의 조건을 각각 검사
• 정답 코드

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

vector<vector<int>> structure;
bool check(int y, int x, int build_type) {
    bool ret = true; // 경계에 아무것도 없는 경우 삭제/설치 가능하므로 기본은 true
    // 기둥 설치 또는 삭제 시 해당 위치에 기둥이 있으면
    if ((structure[y][x] & 1) or build_type == 0) {
        // 바닥이거나 아래에 기둥이 있거나, 양 끝에 보가 하나 있으면 true
        if (y == 0 or (y > 0 and (structure[y-1][x] & 1)) or
            (structure[y][x] & 2) or (x > 0 and (structure[y][x-1] & 2)))
            ret = true;
        else ret = false;
    }
    // 보 설치 또는 삭제 시 해당 위치에 보가 있으면
    if ((structure[y][x] & 2) or build_type == 1) {
        // 양 끝에 기둥이 하나 있거나, 양 끝 모두 보가 있으면 true
        if ((structure[y-1][x] & 1) or (structure[y-1][x+1] & 1) or
           (x > 0 and (structure[y][x-1] & 2) and (structure[y][x+1] & 2)))
            ret = true;
        else ret = false;
    }
    return ret;
}

void build(vector<vector<int>>& build_frame) {
    for (auto& v : build_frame) {
        int x = v[0], y = v[1], a = v[2];
        if (v[3]) {
            if (check(y, x, a))
                structure[y][x] |= 1 << a;
        } else {
            structure[y][x] ^= 1 << a;
            if (a == 0) { // 기둥 삭제 후 조건 검사
                if (check(y+1, x, -1))
                    if (x == 0 or (x > 0 and check(y+1, x-1, -1)))
                        continue;
            } else { // 보 삭제 후 조건 검사
                if (check(y, x, -1) and check(y, x+1, -1))
                    if (x == 0 or (x > 0 and check(y, x-1, -1)))
                        continue;
            }
            structure[y][x] |= 1 << a;
        }
    }
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    structure = vector<vector<int>> (n+2, vector<int> (n+2,0));
    build(build_frame);
    for (int x = 0; x < n+1; x++) {
        for (int y = 0; y < n+1; y++) {
            if (structure[y][x] & 1) answer.push_back({x, y, 0});
            if (structure[y][x] & 2) answer.push_back({x, y, 1});
        }
    }
    return answer;
}