[시뮬레이션] 기둥과 보

해결 방법

먼저, 각 좌표마다 상하로 기둥이 있는지, 좌우로 보가 있는지를 판별할 수 있게 했다. 따라서, 아래와 같은 구조체를 생성해서 좌표마다 배치해줬다.

struct State{
    bool up_column; // 기둥이 존재하는가?
    bool down_column; // 기둥이 받치고 있는가?
    bool left_beam; // 왼쪽으로 보가 연결되어 있는가?
    bool right_beam; // 오른쪽으로 보가 연결되어 있는가?
};

State state[101][101];

 

 

▣ 기둥을 설치할 수 있는 경우

• 기둥 또는 보가 받치고 있다.
• 바닥이다.

 

▣ 보를 설치할 수 있는 경우

• 왼쪽 또는 오른쪽 기둥이 받치고 있다.
• 양쪽 보를 연결할 수 있다.

 

▣ 기둥을 삭제할 수 없는 경우

• 위 좌표에 기둥이 있을 때, 왼쪽 또는 오른쪽 보가 모두 받치고 있지 않다.
• 위 좌표에서 왼쪽으로 보가 연결되어 있을 때, 보의 왼쪽 부분을 기둥이 받치고 있지 않고 보가 양쪽으로 연결되어 있지도 않다.
• 위 좌표에서 오른쪽으로 보가 연결되어 있을 때, 보의 오른쪽 부분을 기둥이 받치고 있지 않고 보가 양쪽으로 연결되어 있지도 않다.

 

▣ 보를 삭제할 수 없는 경우

• 기둥이 세워져 있을 때, 기둥 또는 왼쪽 보가 받치고 있지 않다.
• 오른쪽 좌표에 기둥이 세워져 있을 때, 기둥 또는 오른쪽 보가 받치고 있지 않다.
• 왼쪽으로 보가 연결되어 있을 때, 양쪽 기둥이 왼쪽 보를 받치고 있지 않다.
• 오른쪽으로 보가 연결되어 있을 때, 양쪽 기둥이 오른쪽 보를 받치고 있지 않다.

 

위의 조건들을 모두 반영하면 문제를 해결할 수 있다.

 

 

소스 코드

이해를 돕기 위해 일부러 중첩시킨 if문도 있다.

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

struct State{
    bool up_column;
    bool down_column;
    bool left_beam;
    bool right_beam;
};

State state[101][101];

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    
    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]==1) { // 설치 
            if(build_frame[i][2]==0) { // 기둥
                if(state[x][y].down_column||state[x][y].left_beam||state[x][y].right_beam||y==0) {
                    state[x][y].up_column=true;
                    state[x][y+1].down_column=true;
                }
            } else { // 보
                if(state[x][y].down_column||state[x+1][y].down_column||(state[x][y].left_beam&&state[x+1][y].right_beam)) {
                    state[x][y].right_beam=true;
                    state[x+1][y].left_beam=true;
                }
            }
        } else { // 삭제
            bool check = true;
            if(build_frame[i][2]==0) { // 기둥
                if(state[x][y+1].up_column) {
                    if(!state[x][y+1].left_beam&&!state[x][y+1].right_beam) check=false;
                }
                if(state[x][y+1].left_beam) {
                    if(!state[x-1][y+1].down_column&&!(state[x-1][y+1].left_beam&&state[x][y+1].right_beam)) check=false;
                }
                if(state[x][y+1].right_beam) {
                    if(!state[x+1][y+1].down_column&&!(state[x+1][y+1].right_beam&&state[x][y+1].left_beam)) check=false;
                }
                if(check) {
                    state[x][y].up_column=false;
                    state[x][y+1].down_column=false;
                }
            } else { // 보
                if(state[x][y].up_column) {
                    if(!state[x][y].left_beam&&!state[x][y].down_column) check=false;
                }
                if(state[x+1][y].up_column) {
                    if(!state[x+1][y].right_beam&&!state[x+1][y].down_column) check=false;
                }
                if(state[x][y].left_beam) {
                    if(!state[x][y].down_column&&!state[x-1][y].down_column) check=false;
                }
                if(state[x+1][y].right_beam) {
                    if(!state[x+1][y].down_column&&!state[x+2][y].down_column) check=false;
                }
                if(check) {
                    state[x][y].right_beam=false;
                    state[x+1][y].left_beam=false;
                }
            }
        }
    }
    for(int i=0;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            if(state[i][j].up_column) answer.push_back({i, j, 0});
            if(state[i][j].right_beam) answer.push_back({i, j, 1});
        }
    }
    return answer;
}

 

테스트 케이스 23개 모두 정답

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/60061