프로그래머스 문제 - 기둥과 보 설치

프로그래머스 기둥과 보 설치 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

기둥과 보를 이용하여 벽면 구조물을 세울려고 합니다.
기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return해야 합니다.

문제 풀이

기둥과 보의 설치와 제거를 진행하는 코드를 작성해야 합니다.
벽면의 크기n이 주어지지만 검색하는 부분은 격자가 아닌 격자 사이에 있는 교점을 검색해야 합니다. 그러므로 범위는 0~n이기 때문에 n+1만큼의 배열을 만들어 작업해야 합니다.

이후에 기둥의 생성 조건과 보의 생성 조건을 찾아 코드로 적어야합니다.
기둥은 총 3가지가 있는데

• 설치할 기둥이 바닥일 경우
• 설치할 기둥 밑에 기둥이 있을 경우
• 설치할 기둥에 양쪽 중 한곳이라도 보가 설치되어 있을 경우

가 있습니다.
보는 총 4가지가 있는데

• 설치할 보 밑에 기둥이 설치되어 있는 경우
• 설치할 보 오른쪽 밑에 기둥이 설치되어 있는 경우
• 위 2가지의 경우가 아닌데 왼쪽 벽면에 붙어있다면 설치X
• 설치할 보 왼쪽과 오른쪽에 보가 설치되어 있는 경우

가 있습니다.
이를 함수로 만들어놓고 사용하면 됩니다.

설치는 위와 같은 방법으로 하면 되고 삭제도 진행해야 합니다.
삭제는 기둥이나 보를 삭제하고 모든 구조물들을 확인하여 불가능한 부분이 있는지 확인하는 방법과, 기둥과 보를 삭제하였을 때 영향을 받을 구조물들을 체크하는 방법이 있습니다.
두 번째 방법이 속도가 빠르겠지만 모든 구조물들을 확인하여도 시간초과가 나오지 않으니 첫 번째 방법을 사용하였습니다.

지울 구조물을 먼저 지우고 모든 구조물을 확인 후 한개라도 불가능한 구조물이 나올 경우 지웠던 구조물을 다시 세우면 됩니다.
아마 지울 구조물의 주변 구조물만 체크하면 될 것입니다.

이후 모든 작업을 끝내고 존재하는 구조물들을 [가로좌표, 세로좌표, 0:기둥1:보] 식으로, 가로좌표->세로좌표->기둥먼저 순으로 오름차순 정렬을 진행하면 됩니다.

전체 코드

구현만 하면 통과할 수 있는 코드지만, 구현 자체가 복잡하고 어려운 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> PillarMap;
vector<vector<int>> PillarBeamMap;

bool checkInstallEnable(int x, int y, int kind){
    if(kind == 0)
    {
        if(x == 0)
        {
            return true;
        }
        if(y > 0)
        {
            //설치할 기둥 밑에 기둥이 있는가
            //설치할 기둥 위치에 보가 한개라도 설치되어 있는가
            if(PillarBeamMap[x][y-1] > 0 || PillarBeamMap[x][y] > 0)
            {
                return true;
            }
        }
        if(PillarMap[x-1][y] > 0 || PillarBeamMap[x][y] > 0)
        {
            return true;
        }
    }else
    {
        //설치할 보 밑이나 오른쪽 밑에 기둥이 설치되어 있는가
        if(PillarMap[x-1][y] > 0 || PillarMap[x-1][y+1] > 0)
        {
            return true;
        }else if(y == 0)    //위 상황이 아니고 왼쪽 벽에 붙어있다면
        {
            return false;
        }
        //양쪽으로 보가 존재하는가
        if(PillarBeamMap[x][y-1] > 0 && PillarBeamMap[x][y+1] > 0)
        {
            return true;
        }
    }
    return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    PillarMap.assign(n+1, vector<int>(n+1));
    PillarBeamMap.assign(n+1, vector<int>(n+1));
    
    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(checkInstallEnable(Y, X, build_frame[i][2]))
            {
                build_frame[i][2] == 0 ? PillarMap[Y][X]++ : PillarBeamMap[Y][X]++;
            }
        }else
        {
            //위치의 기둥이나 보를 제외하고 구조물이 가능한지 확인
            build_frame[i][2] == 0 ? PillarMap[Y][X]-- : PillarBeamMap[Y][X]--;
            for(int j = 0; j < n+1; j++)
            {
                for(int k = 0; k < n+1; k++)
                {
                    if(PillarMap[k][j] > 0)
                    {
                        if(!checkInstallEnable(k, j, 0))
                        {
                            build_frame[i][2] == 0 ? PillarMap[Y][X]++ : PillarBeamMap[Y][X]++;
                            j = n+1;
                            k = n+1;
                            break;
                        }
                    }
                    if(PillarBeamMap[k][j] > 0)
                    {
                        if(!checkInstallEnable(k, j, 1))
                        {
                            build_frame[i][2] == 0 ? PillarMap[Y][X]++ : PillarBeamMap[Y][X]++;
                            j = n+1;
                            k = n+1;
                            break;
                        }
                    }
                }
            }
        }
    }
    
    vector<int> v;
    for(int i = 0; i < n+1; i++)
    {
        for(int j = 0; j < n+1; j++)
        {
            if(PillarMap[j][i] > 0)
            {
                v.push_back(i);
                v.push_back(j);
                v.push_back(0);
                answer.push_back(v);
                v.clear();
            }
            if(PillarBeamMap[j][i] > 0)
            {
                v.push_back(i);
                v.push_back(j);
                v.push_back(1);
                answer.push_back(v);
                v.clear();
            }
        }
    }
    
    return answer;
}

출저

https://school.programmers.co.kr/learn/courses/30/lessons/60061