[프로그래머스/C++] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT)

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 보와 기둥을 잘 구분하면 해결되는 문제다.

여기서 보를 건설 할 수 있는 조건은 양쪽에 보가 있거나, 한쪽 끝이 기둥위에 닿아있으면 된다.

 

기둥은 보의 한쪽 끝 위에 세우거나, 바닥, 기둥 위에 세울 수있다.

 

이를 고려해 보와 기둥이 세워졌는지 기록을 할 2차원 vector를 만들었다.

 

그리고 세워지는 위치를 기준으로 아래와 같이 정의했다.

[x ,y]에 기둥이 세워졌다면 이 기둥은 [x, y]와 [x, y+1]을 차지한다는 뜻이다.

[x ,y]에 보가 세워졌다면 이 보는 [x, y]와 [x+1, y]을 차지한다는 뜻이다.

 

이렇게 보나 기둥을 세울 수 있는지 검사하고 세울 수 있다면 보, 기둥을 세우도록 구현했다.

 

삭제도 이와 비슷하게 구현하면 된다.

기둥이나 보를 삭제할 경우 삭제한 구조물이 영향을 미칠 수 있는 보와 기둥들이 세워져 있을 수 있는지 검사하면 된다.

 

[기둥을 삭제할 경우]

 

기둥을 삭제할 경우에는 기둥의 위쪽 좌표를 기준으로 다른 구조물들이 세워질 수 있으므로 3가지 경우로 나눌 수 있다.

기둥의 좌표가 [y, x]일 경우에 기둥의 위쪽은 [y+1,x]다.

 

1. 기둥의 위쪽 부분이 보의 오른쪽일 경우

2. 기둥의 위쪽 부분이 다른 기둥의 아래부분일 경우

3. 기둥의 위쪽 부분이 보의 왼쪽일 경우

 위 그림에 해당하는 구조물들만 계속 세워져 있을 수 있는지 판단하고, 하나라도 세워져 있을 수 없다면, 해당 구조물을 삭제할 수 없다는 의미다.

 

 

[보를 삭제할 경우]

 

보를 삭제하는 경우는 4가지 경우로 나눌 수 있다.

보의 좌표가 [y, x]일 경우에 보의 오른쪽은 [y,x+1]이다.

 

1. 보의 왼쪽에 기둥이 세워져있는 경우

2. 보의 오른쪽에 기둥이 세워져있는 경우

3. 보의 왼쪽에 다른 보가 맞닿은 경우

4. 보의 오른쪽에 다른 보가 맞닿은 경우

마찬가지로 4가지 경우의 구조물들이 계속 세워져 있을 수 있는지 판단하고, 하나라도 세워져 있을 수 없다면, 보를 삭제할 수 없다는 의미다.

 

구조물을 세우는 경우와 삭제하는 경우를 구분해서 구현하면 쉽게 해결되는 문제다.

 

​

[아이디어 정리]

1. 보와 기둥의 위치를 저장할 기준을 잡고, 두 구조물을 구분해 저장할 수 있는 2차원 vector를 만든다.
2. 보와 기둥을 세울 수 있는지 검사하는 코드를 구현한다.
3. 보와 기둥을 삭제할 수 있는지 검사하는 코드를 구현한다.
4. 오름차순으로 return한다.

 

 

Code

 

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

vector<vector<int>> zMap;
vector<vector<int>> oMap;

bool CanBuild(int x, int y, int a, int &n)
{
    if (a==0) //기둥
    {
        if (y==0)
        {
            zMap[x][y]=0;
            return true;
        }
        if (oMap[x][y]==1)
        {
            zMap[x][y]=0;
            return true;
        }
        if (y-1>=0)
        {
            if (zMap[x][y-1]==0)
            {
                zMap[x][y]=0;
                return true;
            }                    
        }
        if (x-1>=0)
        {
            if (oMap[x-1][y]==1)
            {
                zMap[x][y]=0;
                return true;
            }
        }
    }
    else
    { //보 설치조건
        if (y-1>=0)
        {
            if (zMap[x][y-1]==0)
            {
                oMap[x][y]=1;
                return true;
            }
            if (x+1<=n)
            {
                if (zMap[x+1][y-1]==0)
                {
                    oMap[x][y]=1;
                    return true;
                }
            }
        }
        if(x-1>=0&&x+1<=n)
        {
            if (oMap[x-1][y]==1&&oMap[x+1][y]==1)
            {
                oMap[x][y]=1;
                return true;
            }
        }
    }
    return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    zMap=vector<vector<int>>(n+1,vector<int>(n+1,3)); //기둥
    oMap=vector<vector<int>>(n+1,vector<int>(n+1,3)); //보
    for (int i=0; i<build_frame.size(); i++)
    {
        // [2]: 0기둥, 1보, [3]:0삭제, 1설치
        int x,y,a,b;
        x=build_frame[i][0], y=build_frame[i][1], a=build_frame[i][2],b=build_frame[i][3];
        if (b==1)
            CanBuild(x,y,a,n);
        else
        {
            bool flag=true;
            if (a==0) //기둥
            {
                zMap[x][y]=3;
                
                if (y+1<=n&&oMap[x][y+1]==1&&!CanBuild(x,y+1,1,n))
                    flag=false;
                if (y+1<=n&&x-1>=0&&oMap[x-1][y+1]==1&&!CanBuild(x-1,y+1,1,n))
                    flag=false;
                if (y+1<=n&&zMap[x][y+1]==0&&!CanBuild(x,y+1,0,n))
                    flag=false;
                    
                if (!flag)
                    zMap[x][y]=0;
            }
            else if(a==1)
            {
                oMap[x][y]=3;
                
                if (x-1>=0&&oMap[x-1][y]==1&&!CanBuild(x-1,y,1,n))
                    flag=false;
                if (x+1<=n&&oMap[x+1][y]==1&&!CanBuild(x+1,y,1,n))    
                    flag=false;
                if (x+1<=n&&zMap[x+1][y]==0&&!CanBuild(x+1,y,0,n))
                    flag=false;
                if (zMap[x][y]==0&&!CanBuild(x,y,0,n))
                    flag=false;
                
                if (!flag)
                    oMap[x][y]=1;
            }
        }        
    }
    for (int i=0; i<=n; i++)
    {
        for (int j=0; j<=n; j++)
        {
            if (zMap[i][j]==0)
            {
                answer.push_back({i,j,0});
            }
            if (oMap[i][j]==1)
            {
                answer.push_back({i,j,1});
            }
        }
    }
    return answer;
}

 

 

 

Code (전부 검사)

 

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

vector<vector<int>> zMap;
vector<vector<int>> oMap;

bool CanBuild(int x, int y, int a, int &n)
{
    if (a==0) //기둥
    {
        if (y==0)
        {
            zMap[x][y]=0;
            return true;
        }
        if (oMap[x][y]==1)
        {
            zMap[x][y]=0;
            return true;
        }
        if (y-1>=0)
        {
            if (zMap[x][y-1]==0)
            {
                zMap[x][y]=0;
                return true;
            }                    
        }
        if (x-1>=0)
        {
            if (oMap[x-1][y]==1)
            {
                zMap[x][y]=0;
                return true;
            }
        }
    }
    else
    { //보 설치조건
        if (y-1>=0)
        {
            if (zMap[x][y-1]==0)
            {
                oMap[x][y]=1;
                return true;
            }
            if (x+1<=n)
            {
                if (zMap[x+1][y-1]==0)
                {
                    oMap[x][y]=1;
                    return true;
                }
            }
        }
        if(x-1>=0&&x+1<=n)
        {
            if (oMap[x-1][y]==1&&oMap[x+1][y]==1)
            {
                oMap[x][y]=1;
                return true;
            }
        }
    }
    return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    zMap=vector<vector<int>>(n+1,vector<int>(n+1,3)); //기둥
    oMap=vector<vector<int>>(n+1,vector<int>(n+1,3)); //보
    for (int i=0; i<build_frame.size(); i++)
    {
        // [2]: 0기둥, 1보, [3]:0삭제, 1설치
        int x,y,a,b;
        x=build_frame[i][0], y=build_frame[i][1], a=build_frame[i][2],b=build_frame[i][3];
        if (b==1)
            CanBuild(x,y,a,n);
        else
        {
            bool flag=true;
            if (a==1)
            {
                oMap[x][y]=3;
            }
            else
            {
                zMap[x][y]=3;              
            }
            for (int nx=0; nx<=n; nx++)
            {
                for (int ny=0; ny<=n; ny++)
                {
                    if (zMap[nx][ny]==0&&!CanBuild(nx,ny,0,n))
                    {
                        flag=false;
                        break;
                    }
                    if (oMap[nx][ny]==1&&!CanBuild(nx,ny,1,n))
                    {                      
                        flag=false;
                        break;
                    }
                }
            }
            if (!flag)
            {
                if (a==1)
                {
                    oMap[x][y]=1;
                }
                else
                {
                    zMap[x][y]=0;
                }
            }
        }        
    }
    for (int i=0; i<=n; i++)
    {
        for (int j=0; j<=n; j++)
        {
            if (zMap[i][j]==0)
            {
                answer.push_back({i,j,0});
            }
            if (oMap[i][j]==1)
            {
                answer.push_back({i,j,1});
            }
        }
    }
    return answer;
}

 

 

---

 

이 문제를 푸는데 처음에 바로 안풀렸다. 2시간 가까이 생각해도 왜 안풀리는지 모르겠어서, 구조물을 삭제할 때 마다 모든 구조물이 잘 있는지 검사하도록 코드를 구현했다.

모든 구조물을 검사하니 코드가 잘 통과하는 것을 확인하고, 혹시 조건을 빠뜨린게 있나 확인을 했지만 아무리 확인해도 조건이 빠진게 없었다...

결국 왜 오답이 처리됐는지 원인을 찾았는데, 코드 중에서 !가 딱 한개 빠져있었다... 아오;; 

 

 

프로그래머스