[C++로 풀이] 기둥과 보 설치⭐⭐⭐

📌 기둥과 보 설치

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

추가

• “기둥”을 추가할 때
  • 기둥의 3 가지 조건 중 하나라도 만족하는지 추가하려는 기둥을 검사 하고 기둥을 추가한다.
• “보”를 추가할 때
  • 보의 2 가지 조건 중 하나라도 만족하는지 추가하려는 보를 검사 하고 기둥을 추가한다.

삭제

이 기둥 혹은 보를 먼저 삭제시키고, 삭제시키고난 후에 주변 기둥들과 보들이 조건을 위배하게 되진 않았는지를 검사한다. 하나라도 위배가 되면 이 기둥 혹은 보를 삭제하면 모순이 생긴다는 것임으로 삭제를 다시 취소하면 된다!

• “기둥”을 삭제할 때
  1. 기둥의 3 가지 조건 중 하나라도 만족하는지 삭제한 기둥의 위 쪽 기둥을 검사 하고 모두 만족하지 못하다면 이 기둥을 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
  2. 보의 2 가지 조건 중 하나라도 만족하는지 삭제한 기둥이 왼 쪽에 오는 위 쪽 보를 검사 하고 모두 만족하지 못하다면 이 기둥을 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
  3. 보의 2 가지 조건 중 하나라도 만족하는지 삭제한 기둥이 오른 쪽에 오는 위 쪽 보를 검사 하고 모두 만족하지 못하다면 이 기둥을 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
• “보”를 삭제할 때
  1. 기둥의 3 가지 조건 중 하나라도 만족하는지 삭제한 보의 왼 쪽 위의 기둥을 검사 하고 모두 만족하지 못하다면 이 보를 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
  2. 기둥의 3 가지 조건 중 하나라도 만족하는지 삭제한 보의 오른 쪽 위의 기둥을 검사 하고 모두 만족하지 못하다면 이 보를 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
  3. 보의 2 가지 조건 중 하나라도 만족하는지 삭제한 보의 왼쪽에 연결된 보를 검사 하고 모두 만족하지 못하다면 이 보를 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
  4. 보의 2 가지 조건 중 하나라도 만족하는지 삭제한 보의 오른쪽에 연결된 보를 검사 하고 모두 만족하지 못하다면 이 보를 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.

---

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool board[101][101][2]; // [x][y][0] 기둥  [x][y][1] 보
int num = 0; // 벽면 사이즈

bool IsColumnOK(int x, int y) {
    bool cond1 = y == 0;
    bool cond2 = board[x][y][1] || (x - 1 >= 0 && board[x - 1][y][1]);
    bool cond3 = y - 1 >= 0 && board[x][y - 1][0];
    return cond1 || cond2 || cond3;
}

bool IsPaperOK(int x, int y) {
    bool cond1 = (board[x][y - 1][0] || (x + 1 <= num && board[x + 1][y - 1][0])); // y - 1 생략
    bool cond2 = (x - 1 >= 0 && board[x - 1][y][1]) && (x + 1 <= num && board[x + 1][y][1]);
    return cond1 || cond2;
}

bool compare(vector<int> a, vector<int> b) {
    if (a[0] == b[0] && a[1] == b[1])
        return a[2] < b[2];
    if (a[0] == b[0])
        return a[1] < b[1];
    return a[0] < b[0];
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    num = n;
    for (int i = 0; i < build_frame.size(); ++i) {
        int x = build_frame[i][0];
        int y = build_frame[i][1];
        if (build_frame[i][3] == 0) {
            if (build_frame[i][2] == 0) { // 기둥 삭제
                if (!board[x][y][0])
                    continue;

                board[x][y][0] = false; // 삭제
                if (y + 1 <= n && board[x][y + 1][0] && !IsColumnOK(x, y + 1)) {
                    board[x][y][0] = true; // 삭제취소
                    continue;
                }
                if (y + 1 <= n && board[x][y + 1][1] && !IsPaperOK(x, y + 1)) {
                    board[x][y][0] = true; // 삭제취소
                    continue;
                }
                if (x - 1 >= 0 && y + 1 <= n && board[x - 1][y + 1][1] && !IsPaperOK(x - 1, y + 1)) {
                    board[x][y][0] = true; // 삭제취소
                    continue;
                }
            }
            else {  // 보 삭제
                if (!board[x][y][1])
                    continue;

                board[x][y][1] = false; // 삭제
                if (board[x][y][0] && !IsColumnOK(x, y)) {
                    board[x][y][1] = true; // 삭제취소
                    continue;
                }
                if (x + 1 <= n && board[x + 1][y][0] && !IsColumnOK(x + 1, y)) {
                    board[x][y][1] = true; // 삭제취소
                    continue;
                }
                if (x - 1 >= 0 && board[x - 1][y][1] && !IsPaperOK(x - 1, y)) {
                    board[x][y][1] = true; // 삭제취소
                    continue;
                }
                if (x + 1 <= n && board[x + 1][y][1] && !IsPaperOK(x + 1, y)) {
                    board[x][y][1] = true; // 삭제취소
                    continue;
                }
            }
        }
        else {
            if (build_frame[i][2] == 0) { // 기둥 추가
                if (IsColumnOK(x, y))
                    board[x][y][0] = true;
            }
            else {  // 보 추가
                if (IsPaperOK(x, y))
                    board[x][y][1] = true;
            }
        }
    }

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (board[i][j][0]) {
                vector<int> v(3);
                v[0] = i;
                v[1] = j;
                v[2] = 0;
                answer.push_back(v);
            }
            if (board[i][j][1]) {
                vector<int> v(3);
                v[0] = i;
                v[1] = j;
                v[2] = 1;
                answer.push_back(v);
            }
        }
    }

    sort(answer.begin(), answer.end(), compare);

    return answer;
}

✈ 조건을 검사하는 함수

매우매우매우 중요한 부분인데, 이 문제는 num을 포함한다! 즉 이 벽면의 사이즈가 5 x 5 라면 0,1,2,3,4,5 이렇게 5까지 좌표에 포함된다는 것이다!!!!! 이에 대해 생각을 못하고 평소처럼 범위를 벗어나지 않는 조건으로 x + 1 < num 이런 식으로 잡는 바람에 틀렸었는데 원인 찾느라 애먹었다.. 😭 x + 1 <= num 이라고 해야 한다.

따라서 배열은 (n + 1) x (n + 1) 크기로 선언이 되야 한다. 벽면의 최대 사이즈는 100 이라고 문제에서 주어져서 나는 그냥 bool board[101][101][2] 101 x 101 크기로 선언했다. [x][y][0] 은 기둥 자리이고, [x][y][1]은 보 자리이다. 이 board에 기둥 혹은 보가 현재 벽면에 추가되어 있는 상태라면, 즉 존재하는 상태라면 해당 자리가 true 인 상태이다. 예를들어 [x][y][0]가 true 이면 (x, y)에 기둥이 현재 존재한다는 뜻이다. 삭제 또한 이 값을 false 로 만들어주는 식으로 처리할 것이다.

bool board[101][101][2]; // [x][y][0] 기둥  [x][y][1] 보
int num = 0;

/* (x, y)에 위치한 기둥의 조건을 검사하는 함수 */
bool IsColumnOK(int x, int y) {
    // 1. 바닥 위에 있거나
    bool cond1 = y == 0;  

    // 2. 보의 한쪽 끝 부분에 있거나 
    // (기둥이 보의 왼쪽에 있다면 이 보는 board[x][y][1])
    // (기둥이 보의 오른쪽에 있다면 이 보는 board[x - 1][y][1])
    bool cond2 = board[x][y][1] || (x - 1 >= 0 && board[x - 1][y][1]);

    // 3. 다른 기둥 위에 있어야 한다. (즉, 아래쪽에 기둥이 있어야 한다.)
    bool cond3 = y - 1 >= 0 && board[x][y - 1][0];

    return cond1 || cond2 || cond3; // 위 3 가지 조건 중 하나만이라도 만족하면 된다.
}

/* (x, y)에 위치한 보의 조건을 검사하는 함수 */
bool IsPaperOK(int x, int y) {
    // 1. 한쪽 끝 부분이 기둥위에 있거나
    // (보의 왼쪽 아래에 기둥이 있다면 이 기둥은 board[x][y - 1][0])
    // (보의 오른쪽 아래에 기둥이 있다면 이 기둥은 board[x + 1][y - 1][0]))
    // 문제에서 바닥에 보를 설치하는 경우는 없다고 주어졌기 때문에 y - 1 >= 0 조건은 따로 두지 않았다.
    bool cond1 = (board[x][y - 1][0] || (x + 1 <= num && board[x + 1][y - 1][0])); 

    // 2. 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.
    // (이 보의 왼쪽 보와도, 오른쪽 보와도 동시에 연결되어 있어야 한다.)
    bool cond2 = (x - 1 >= 0 && board[x - 1][y][1]) && (x + 1 <= num && board[x + 1][y][1]);

    return cond1 || cond2; // 위 2 가지 조건 중 하나만이라도 만족하면 된다.
}

✈ 기둥 삭제

        int x = build_frame[i][0];
        int y = build_frame[i][1];
        if (build_frame[i][3] == 0) { // 삭제
            if (build_frame[i][2] == 0) { // 기둥 삭제
                if (!board[x][y][0]) // 삭제하려는 기둥이 벽면에 존재하지 않는다면 넘어가기
                    continue;

                board[x][y][0] = false; // 삭제해보고

                if (y + 1 <= n && board[x][y + 1][0] && !IsColumnOK(x, y + 1)) { // 삭제한 기둥의 위 쪽 기둥에 모순이 생기는지 검사
                    board[x][y][0] = true; // 모순이 생긴다면 삭제 취소
                    continue;
                }
                if (y + 1 <= n && board[x][y + 1][1] && !IsPaperOK(x, y + 1)) { // 삭제한 기둥이 왼 쪽에 오는 위 쪽 보가 모순이 생기는지 검사
                    board[x][y][0] = true; // 모순이 생긴다면 삭제 취소
                    continue;
                }
                if (x - 1 >= 0 && y + 1 <= n && board[x - 1][y + 1][1] && !IsPaperOK(x - 1, y + 1)) { // 삭제한 기둥이 오른 쪽에 오는 위 쪽 보가 모순이 생기는지 검사
                    board[x][y][0] = true; // 모순이 생긴다면 삭제 취소
                    continue;
                }
            }

✈ 보 삭제

        int x = build_frame[i][0];
        int y = build_frame[i][1];
        if (build_frame[i][3] == 0) { // 삭제
            if (build_frame[i][2] == 1) {  // 보 삭제
                if (!board[x][y][1]) // 삭제하려는 보가 벽면에 존재하지 않는다면 넘어가기
                    continue;

                board[x][y][1] = false; // 삭제해보고

                if (board[x][y][0] && !IsColumnOK(x, y)) { // 삭제한 보의 왼 쪽 위의 기둥에 모순이 생기는지 검사
                    board[x][y][1] = true; // 모순이 생긴다면 삭제 취소
                    continue;
                }
                if (x + 1 <= n && board[x + 1][y][0] && !IsColumnOK(x + 1, y)) { // 삭제한 보의 오른 쪽 위의 기둥에 모순이 생기는지 검사
                    board[x][y][1] = true; // 모순이 생긴다면 삭제 취소
                    continue;
                }
                if (x - 1 >= 0 && board[x - 1][y][1] && !IsPaperOK(x - 1, y)) {  // 삭제한 보의 왼쪽에 연결된 보에 모순이 생기는지 검사
                    board[x][y][1] = true; // 모순이 생긴다면 삭제 취소
                    continue;
                }
                if (x + 1 <= n && board[x + 1][y][1] && !IsPaperOK(x + 1, y)) { // 삭제한 보의 오른쪽에 연결된 보에 모순이 생기는지 검사
                    board[x][y][1] = true; // 모순이 생긴다면 삭제 취소
                    continue;
                }
            }

✈ 기둥, 보 추가

        else {
            if (build_frame[i][2] == 0) { // 기둥 추가
                if (IsColumnOK(x, y)) // 추가하려는 기둥 검사
                    board[x][y][0] = true; // 괜찮다면 추가 완료
            }
            else {  // 보 추가
                if (IsPaperOK(x, y)) // 추가하려는 보 검사
                    board[x][y][1] = true; // 괜찮다면 추가 완료
            }
        }

✈ answer 에 출력하기

    // 0 ~ n 행, 0 ~ n 열 차례대로
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (board[i][j][0]) {  // 기둥이라면
                vector<int> v(3);
                v[0] = i;
                v[1] = j;
                v[2] = 0;
                answer.push_back(v);
            }
            if (board[i][j][1]) {  // 보라면
                vector<int> v(3);
                v[0] = i;
                v[1] = j;
                v[2] = 1;
                answer.push_back(v);
            }
        }
    }

✈ 정렬하기

정렬 조건은 이러했다.

bool compare(vector<int> a, vector<int> b) {
    if (a[0] == b[0] && a[1] == b[1])
        return a[2] < b[2];
    if (a[0] == b[0])
        return a[1] < b[1];
    return a[0] < b[0];
}

//...

sort(answer.begin(), answer.end(), compare);

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기