[ 프로그래머스 기둥과 보 설치 (Lv3) ] (C++)

프로그래머스의 기둥과 보 설치 (Lv3) 문제이다.

[ 문제풀이 ]

명령어에 맞게 기둥과 보를 설치 하거나 제거한 후, 최종적으로 남아있는 구조물들에 대한 정보를 출력해야 하는 문제이다.

설명하기에 앞서, 설명을 할 때 헷갈릴 수 있는 부분에 대해서 한번 정리를 해보고 시작하자.

1. 좌표 표현.

- 주어진 맵에서 가장 왼쪽 위를 (0, 0), 가장 오른쪽 아래를 (N, M), 가장 왼쪽 위에서 오른쪽으로 한칸 움직인 좌표를

  (x , y + 1) , 가장 왼쪽 위에서 아래쪽으로 한칸 움직인 좌표를 (x + 1 , y) 로 표현하겠다.

  주어진 맵을 보면, x좌표가 반대로 되어있긴 하다. 가장 왼쪽 위가 (5, 0)으로 적혀있는데, 이는 입력을 받을 때,

  x좌표를 뒤집어 준 상태로 계산을 하면 되고, 최종적으로 출력할 때, 다시한번 그 좌표를 뒤집어 주기만 하면 되므로

  상관이 없다. 그리고 맵의 크기가 N * N 크기의 맵이라고 가정하고 진행하겠다.

2. 기둥과 보 표현

- 지금부터 기둥으로 Pole[][] 로, 보를 Bo[][] 로 표현하겠다.

  기둥은 주어진 좌표에서 위쪽으로 방향으로 설치를 하기 때문에 예를 들어서 (x , y) 에 기둥을 설치한다고

  가정한다면, Pole[x][y] = true 로 표현할 것이고, 이는 (x , y)와 (x - 1 , y)를 이어주는 기둥이 설치되어 있다는 것을

  의미한다.

  보는 오른쪽 방향으로 설치를 하기 때문에 예를 들어서 (x , y)에 보를 설치한다고 가정한다면, Bo[x][y] = true로 표현할

  것이고, 이는 (x , y)와 (x , y + 1)을 이어주는 보가 설치되어 있다는 것을 의미한다.

  지금부터는 기둥과 보를 위와 같이 표현하도록 하겠다.

그럼 지금부터 기둥을 설치하는 과정, 보를 설치하는 과정, 기둥을 제거하는 과정, 보를 제거하는 과정을 순차적으로 알아보자.

#기둥 설치하기 : (x , y)에 설치

먼저 기둥을 설치할 수 있는 조건에 대해서 부터 다시한번 확인해보자.

1. 기둥은 바닥위에 설치할 수 있다.

2. 기둥은 보의 한쪽 끝 부분에 설치할 수 있다.

3. 기둥은 다른 기둥위에 설치할 수 있다.

우리가 위에서 이야기했던 표현 방식으로 위의 조건들을 이야기해보자.

1. 기둥은 바닥위에 설치할 수 있다.

- x = N 일 경우에 설치가 가능하다는 것을 의미한다. 주어진 x좌표가 맵의 가장 바닥인 좌표를 의미한다면, 즉 x의 값이

  N일 경우에는 설치가 가능하다.

2. 기둥은 보의 한쪽 끝 부분에 설치할 수 있다.

- 기둥은 보의 한쪽 끝 부분에 설치할 수 있는데, 이 때는 2가지 경우가 존재한다.

  .

   위의 그림과 같이, (x , y)에 기둥을 설치할 때, 기둥이 보의 한쪽 끝 부분에 있다면, 그 경우는 2가지가 있다.

   빨강색 보의 오른쪽 끝에 있는 경우, 파랑색 보의 왼쪽 끝에 있는 경우가 존재하는 것이다.

   그럼, 빨강색 보는 Bo[x][y - 1] = true 로 표현할 수 있다. 반대로 파랑색 보는 Bo[x][y] = true 로 표현할 수 있다.

   즉 ! Bo[x][y - 1] = true 이거나, Bo[x][y] = true 라면 기둥을 설치할 수 있다는 것이다.

3. 기둥은 다른 기둥위에 설치할 수 있다.

- 우리가 (x , y)에 기둥을 설치하는데, 이를 또 다른 기둥 위에 설치하는 경우라고 생각해보자.

  그럼 (x , y) 아래에 기둥이 하나 더 설치되어 있어야 한다는 것을 의미한다.

  이를 수식으로 표현해보면 Pole[x + 1][y] = true가 된다. 즉 ! Pole[x + 1][y] = true 인 경우 기둥을 설치할 수 있다는

  것이다.

# 보 설치하기 : (x , y)에 설치

먼저 보를 설치할 수 있는 조건을 다시한번 확인해보자.

1. 보는 한쪽 끝 부분에 기둥이 있으면 설치할 수 있다.

2. 보는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있으면 설치할 수 있다.

그럼 이 또한, 우리가 이야기했던 표현방식으로 이야기해보자.

1. 보는 한쪽 끝 부분에 기둥이 있으면 설치할 수 있다.

이 경우에는 2가지 경우가 발생한다.

.

위의 그림과 같이 검정색 보를 설치하려고 할 때, 왼쪽 끝 부분에 빨강색 기둥이 있거나, 오른쪽 끝 부분에 파랑색 기둥이 있으면 설치가 가능하다.

그럼 이를 수식으로 나타내보면, Pole[x + 1][y] = true 이거나 Pole[x + 1][y + 1] = true 일 때 ,설치가 가능하다는 것을 의미한다. 헷갈릴 거 같아서 다시한번 이야기해보면, Pole[x][y] = true 의 의미는 "(x , y)에서 (x - 1 , y)와 연결된 기둥이 설치되어 있습니다" 를 의미한다. 즉, 위의 그림에서 빨강색 기둥을 Pole[][]로 표현한다면, Pole[x + 1][y] = true가 된다.

왜냐하면, 빨강색 기둥은 (x + 1 , y) ~ (x , y)를 잇는 기둥이기 때문이다.

반대로 파랑색 기둥은 (x + 1 , y + 1)  ~ (x + 1 , y) 를 잇는 기둥이기 때문에 Pole[][]로 표현해보면, Pole[x + 1][y + 1] = true 가 되는 것이다.

2. 보는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있으면 설치할 수 있다.

그럼, Bo[x][y - 1] = true 이고 Bo[x][y + 1] = true 이면 설치를 할 수 있다는 것을 의미한다.

(x , y)에 보를 설치하기 위해서 양쪽 끝이 다른 보들과 연결되어 있다면,

이는, (x , y - 1) ~ (x , y)를 잇는 보가 설치되어 있어야 하고, (x , y + 1) ~ (x , y + 2)를 연결하는 보가 설치되어 있어야 한다는 것을 의미하기 때문이다.

정리해보자 !

[ 기둥 설치하기 ]

1. x == N 일 경우 설치 가능

2. Bo[x][y - 1] = true 일 경우 설치 가능.

3. Bo[x][y] = true 일 경우 설치 가능.

4. Pole[x + 1][y] = true 일 경우 설치 가능.

[ 보 설치하기 ]

1. Pole[x + 1][y] = true 일 경우 설치 가능.

2. Pole[x + 1][y + 1] = true 일 경우 설치 가능.

3. Bo[x][y - 1] = true & Bo[x][y + 1] = true 일 경우 설치 가능.

그럼 이제는 구조물을 제거하는 과정으로 넘어가보자.

제거하는 과정에 대한 전체적인 방법을 하나 이야기해보자면, 위에서 했던 "설치가 가능한 조건문"들을 이용해서 제거가 가능한지 판단해줄 것이다. 구체적으로 알아보자.

예를 들어서 내가 현재 기둥 하나를 제거하려고 한다. 그럼, 그 기둥을 제거해버리고 나머지 기존에 설치된 구조물들에 대해서 설치가 가능한지 판단을 해보는 것이다. 그래서 만약, 기존에 구조물들 중에서, 갑자기 설치할 수 없는 구조물이라고 판단되는 경우가 발생한다면 ? 그 구조물은 "제거해버린 기둥에 의해서 설치가 가능한 구조물" 이라는 것을 의미하고, 이 경우에는 이 기둥을 제거해버리면 구조물이 유지가 안되기 때문에 제거할 수 없다고 판단하는 것이다.

그럼, 반대로 모든 구조물들이 설치가 가능하다면 ? 해당 기둥은 제거해도 되는 구조물이라는 것을 의미한다.

그럼 여기서 우리는 한가지 미리 알고 있어야할 정보가 필요하다.

바로, "기존에 설치되어 있는 구조물들에 대한 정보" 이다. 어느 좌표에, 어느 구조물이 설치되어있는지를 알고 있어야 한다. 그래야만 위에서 말한 판단이 가능하다.

따라서, 본인은 이를 저장하기 위해서 vector를 하나 만들어서 저장해 주었다.

vector에서 관리하는 자료형을 구조체를 만들어서 설정해 주었다.

해당 구조체에서는 { x좌표 , y좌표 , 기둥 or 보 , 존재하는 구조물인지 } 4개를 멤버변수로 만들어 주었다.

최종적으로 남아있는 구조물 또한, 위에서 이야기한 vector에 저장되어 있다.

vector를 정답출력을 위한 조건에 맞게 정렬시켜 준 후, 존재하는 구조물에 한해서 저장 후, return 시켜주면 된다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
#define MAX 110
using namespace std;
 
int N;
int Pole[MAX][MAX];
int Bo[MAX][MAX];
 
struct STRUCTURE
{
    int x;
    int y;
    int Shape;
    int Exist;
};
 
vector<STRUCTURE> List;
 
bool Check_Install_Pole(int x, int y)
{
    if (x == N) return true;
    if (y - 1 >= 0 && Bo[x][y - 1] == true) return true;
    if (Bo[x][y] == true) return true;
    if (Pole[x + 1][y] == true) return true;
    return false;
}
 
bool Check_Install_Bo(int x, int y)
{
    if (Pole[x + 1][y] == true) return true;
    if (y + 1 <= N && Pole[x + 1][y + 1] == true) return true;
    if (Bo[x][y - 1] == true && Bo[x][y + 1] == true) return true;
    return false;
}
 
void Check_Delete_Pole(int x, int y)
{
    int Idx = 0;
    Pole[x][y] = false;
    for (int i = 0; i < List.size(); i++)
    {
        int Lx = List[i].x;
        int Ly = List[i].y;
        int LShape = List[i].Shape;
        if (x == Lx && y == Ly && LShape == 0)
        {
            Idx = i;
            continue;
        }
        if (List[i].Exist == -1) continue;
 
        if (LShape == 0 && Check_Install_Pole(Lx, Ly) == false)
        {
            Pole[x][y] = true;
            return ;
        }
        if (LShape == 1 && Check_Install_Bo(Lx, Ly) == false)
        {
            Pole[x][y] = true;
            return ;
        }
    }
    List[Idx].Exist = -1;
}
 
void Check_Delete_Bo(int x, int y)
{
    int Idx = 0;
    Bo[x][y] = false;
    for (int i = 0; i < List.size(); i++)
    {
        int Lx = List[i].x;
        int Ly = List[i].y;
        int LShape = List[i].Shape;
        if (x == Lx && y == Ly && LShape == 1)
        {
            Idx = i;
            continue;
        }
        if (List[i].Exist == -1) continue;
 
        if (LShape == 0 && Check_Install_Pole(Lx, Ly) == false)
        {
            Bo[x][y] = true;
            return;
        }
        if (LShape == 1 && Check_Install_Bo(Lx, Ly) == false)
        {
            Bo[x][y] = true;
            return;
        }
    }
    List[Idx].Exist = -1;
}
 
bool Compare(STRUCTURE A, STRUCTURE B)
{
    if (A.Exist >= B.Exist)
    {
        if (A.Exist == B.Exist)
        {
            if (A.y <= B.y)
            {
                if (A.y == B.y)
                {
                    if (A.x >= B.x)
                    {
                        if (A.x == B.x)
                        {
                            if (A.Shape < B.Shape)
                            {
                                return true;
                            }
                            return false;
                        }
                        return true;
                    }
                    return false;
                }
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}
 
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) 
{
    N = n;
    List.clear();
    vector<vector<int>> answer;
    for (int i = 0; i < build_frame.size(); i++)
    {
        int x = build_frame[i][1];
        int y = build_frame[i][0];
        int Shape = build_frame[i][2];
        int Install = build_frame[i][3];
        x = n - x;
        
        if (Install == 1)
        {
            if (Shape == 0 && Check_Install_Pole(x, y) == true)
            {
                List.push_back({ x, y, Shape, 1 });
                Pole[x][y] = true;
            }
            if (Shape == 1 && Check_Install_Bo(x, y) == true)
            {
                List.push_back({ x, y, Shape, 1 });
                Bo[x][y] = true;
            }
        }
        else
        {
            if (Shape == 0) Check_Delete_Pole(x, y);
            if (Shape == 1) Check_Delete_Bo(x, y);
        }
    }
    sort(List.begin(), List.end(), Compare);
    for (int i = 0; i < List.size(); i++)
    {
        if (List[i].Exist == -1) break;
        answer.push_back({ List[i].y, N - List[i].x, List[i].Shape });
    }
    return answer;
}