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

 

해당 문제는 2020 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

 

해설

시뮬레이션 문제로 문제에서 주어진 사항대로 구현하면 된다.

핵심 로직은 기둥과 보를 특정 위치에 추가하거나 삭제하는 것이 가능한지 확인하는 부분이다.

 

(x, y)에 기둥이 있는지 여부를 pil[x][y], 보가 있는지 여부를 pan[x][y]로 저장할 떄, 

 

1. 기둥이 (x, y)에 존재할 수 있으려면,

1) 기둥이 바닥에 있거나: x == 0

2) 보 위에 있거나: pan[x][y-1] || pan[x][y]

3) 다른 기둥 위에 있어야 한다: pil[x-1][y]

 

2.  보가 (x, y)에 존재할 수 있으려면,

1) 밑에 기둥이 있거나: pil[x-1][y] || pil[x-1][y+1]

2) 양 옆에 보가 있어야 한다: pan[x][y-1] && pan[x][y+1]

 

(x, y) 위치에 기둥이나 보를 설치하는 경우, 위의 조건을 확인한다. 조건을 만족하면 pil[x][y](or pan[x][y])를 true로 변경시킨다.

(x, y) 위치에서 기둥이나 보를 삭제하는 경우, 먼저 pil[x][y](or pan[x][y])를 false로 만든다. 전체 좌표를 순회하면서 각각의 자리에 있는 기둥과 보가 위의 조건을 만족하는지 살핀 후 모두 만족한다면 삭제를 완료한다. 전체 좌표 중 하나라도 위의 조건을 만족하지 않는다면 삭제를 취소하고 pil[x][y](or pan[x][y])를 다시 true로 변경한다.

 

pil과 pan 배열을 순회하며 값이 true일 때 (x, y, 기둥과 보 여부)를 벡터에 추가한다. 이를 오름차순으로 정렬하여 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

bool pan[110][110];
bool pil[110][110];

bool OOB(int x, int y, int n) {
    return x < 0 || x > n || y < 0 || y > n;
}

bool pillar(int x, int y, int n) {

    if (x == 0) return true;
    if (!OOB(x, y-1, n) && pan[x][y-1] || pan[x][y]) return true;
    if (!OOB(x-1, y, n) && pil[x-1][y]) return true;
    return false;
}

bool panel(int x, int y, int n) {

    if (!OOB(x-1, y, n) && pil[x-1][y]) return true;
    if (!OOB(x-1, y+1, n) && pil[x-1][y+1]) return true;
    if (!OOB(x, y-1, n) && !OOB(x, y+1, n) && pan[x][y-1] && pan[x][y+1]) return true;
    return false;    
}

void add(int x, int y, int a, int n) {

    if (a == 0 && pillar(x, y, n)) pil[x][y] = true;
    if (a == 1 && panel(x, y, n)) pan[x][y] = true;
}

void del(int x, int y, int a, int n) {

    if (a == 0) pil[x][y] = false;
    else pan[x][y] = false;

    bool flag = true;
    for (int i=0; i<=n; i++) {
        for (int j=0; j<=n; j++) {
            if (pil[i][j] && !pillar(i, j, n)) flag = false;
            if (pan[i][j] && !panel(i, j, n)) flag = false;
        }
    }

    if (!flag) {
        if (a == 0) pil[x][y] = true;
        else pan[x][y] = true;
    }
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {

    for (const auto& v : build_frame) {
        if (v[3] == 1) add(v[1], v[0], v[2], n);
        else del(v[1], v[0], v[2], n);
    }

    vector<vector<int>> ans;
    for (int i=0; i<=n; i++)  {
        for (int j=0; j<=n; j++) {
            if (pil[i][j]) ans.push_back({j, i, 0});
            if (pan[i][j]) ans.push_back({j, i, 1});
        }
    }
    sort(ans.begin(), ans.end());
    return ans;
}