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

문제

프로그래머스 2020 KAKAO BLIND RECRUITMENT - 기둥과 보 설치 (Level 3)

코딩테스트 연습 - 기둥과 보 설치

 

---

문제 풀이

접근 방식

이 문제는 2020 카카오 블라인드 공채 1차 코딩테스트 5번 문제로,

아래의 규칙을 준수하여 구조물을 설치하는 문제였다.

 

구조물 설치 규칙

 

우선, 위의 규칙대로 기둥과 보를 설치하기 위해

map을 3차원 벡터로 만들어서 기둥과 보에 대한 정보를 각각 저장해주었다.

 

수행해야 하는 작업은 삭제와 설치였다. 삭제는 주어진 좌표의 구조물을 삭제하는 것인데,

삭제 후에 남아있는 구조물이 위의 규칙에 위배되는 경우에는 삭제를 할 수 없다.

그래서 구조물을 먼저 삭제한 후, map에 있는 모든 구조물 탐색하며 규칙에 위배되는 구조물이 있는지 확인해주었고,

규칙에 위배되는 구조물이 있는 경우에는 삭제한 구조물을 다시 설치해주었다.

설치의 경우에는 주어진 위치에 해당 구조물을 설치할 수 있는지를 먼저 확인해준 후 설치를 수행하였다.

 

규칙에 위배되는 경우인지는 check 함수를 통해 확인해주었다.

check 함수는 기둥인 경우와 보인 경우로 나눠서 아래와 같이 구현해주었다.

bool check(int x, int y, int a){
    if(a == 0){     // 기둥
        if(!y || (y-1 >= 0 && map[0][x][y-1])
           || map[1][x][y] || (x-1 >= 0 && map[1][x-1][y]))
            return true;
    }
    else{           // 보
        if((y-1 >= 0 && map[0][x][y-1]) || (y-1 >= 0 && map[0][x+1][y-1])
            || (x-1 >= 0 && map[1][x-1][y] && map[1][x+1][y]))
            return true;
    }
    return false;
}

 

---

풀이 코드 - C++

#include <vector>
using namespace std;

vector<vector<vector<int>>> map;

bool check(int x, int y, int a){
    if(a == 0){     // 기둥
        if(!y || (y-1 >= 0 && map[0][x][y-1])
           || map[1][x][y] || (x-1 >= 0 && map[1][x-1][y]))
            return true;
    }
    else{           // 보
        if((y-1 >= 0 && map[0][x][y-1]) || (y-1 >= 0 && map[0][x+1][y-1])
            || (x-1 >= 0 && map[1][x-1][y] && map[1][x+1][y]))
            return true;
    }
    return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    map.assign(2,vector<vector<int>>(n+1,vector<int>(n+1)));
    int len = build_frame.size();
    int x, y, a, b;
    for(int i = 0; i < len; i++){
        x = build_frame[i][0]; y = build_frame[i][1];
        a = build_frame[i][2]; b = build_frame[i][3];
        if(b == 0){     // 삭제            
            map[a][x][y] = 0;
            for(int i = 0; i <= n; i++){
                for(int j = 0; j <= n; j++){
                    for(int k = 0; k < 2; k++){
                        if(map[a][x][y] == 1) break;
                        if(map[k][i][j] == 1 && !check(i,j,k))
                            map[a][x][y] = 1;
                    }
                }
            }
        }
        else{           // 설치
            if(check(x,y,a)) map[a][x][y] = 1;
        }
    }
    
    // 정답 벡터에 저장
    vector<vector<int>> answer;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k < 2; k++){
                if(map[k][i][j] == 1)
                    answer.push_back({i,j,k});
            }
        }
    }
    return answer;
}

실행 결과