[2020 kakao blind recruitment] lv3 기둥과 보 설치(cpp/python)

기둥과 보 설치

문제 설명

구현 문제이다. 머릿속으로 구현은 나름 빠르게 됐는데 코드로 옮기면서 조건을 한 두개씩 빼먹어서 시간이 오래걸렸다. 시험이 아닌데도 3시간씩 걸려서 푸는데.. 언제 이런문제를 1시간 안에 풀 수 있을까...

기둥과 보가 설치될 수 있는 조건을 명확하게 해결하여야한다.

설치할 때는 해당 위치에 기둥과 보가 설치될 수 있는지 확인하고, 삭제할 때는 삭제를 시킨 후 모든 구역에 대해 기둥과 보가 설치 할 수 있는지 없는지 확인한다.

문제 풀이

소스코드 : C++

1. 해당 좌표에 기둥과 보가 설치 되어있는지 확인하는 구조체 POS Map[101][101]을 선언한다.
2. 우선 해당 좌표에 기둥과 보를 설치할 수 있는지 확인하는 두 함수 chk_pillar와 chk_beam을 구현한다.
   1. chk_pillar
      • 바닥인 경우
      • 해당위치에 보가 있는 경우
      • 해당위치의 왼쪽에 보가 있는경우 (이렇게 나누는 이유는 보는 왼쪽에서 오른쪽으로 설치한다가 기준)
      • 아래쪽에 기둥이 있는 경우
   2. chk_beam
      • 해당 위치의 아래쪽에 기둥이 있는 경우
      • 해당 위치의 오른쪽 아래에 기둥이 있는 경우
      • 해당 위치의 왼쪽과 오른쪽에 모두 보가 있는 경우
3. build_frame을 탐색한다.
4. 설치인 경우에 조건에 맞춰 해당위치에 기둥 혹은 보를 설치한다.
5. 삭제하는 경우에 해당위치의 기둥 혹은 보를 삭제한다.
6. 삭제한 후 모든 구역에 대해 기둥과 보가 있다면 존재여부를 탐색한다.
7. 존재할 수 없는 경우가 발생하면 바로 break를 걸어 다음 build_frame을 탐색한다
8. 모든 탐색이 끝나면 모든 위치에 대해 기둥과 보의 존재를 answer에 넣어준다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct POS{
    bool pillar;
    bool beam;
};   // 기둥, 보의 이어진 위치
POS Map[101][101];

bool chk_pillar(int y, int x){    
    bool ret = false;
    if(y==0) ret = true;    // 바닥이면
    else {
        if(Map[y][x].beam)  ret = true;   //보가 있으면
        if(Map[y][x-1].beam) ret = true; //왼쪽에 보가 있으면
        if(Map[y-1][x].pillar) ret= true; //아래에 기둥이 있으면
    }
    return ret;
}
bool chk_beam(int y, int x, int n){
    bool ret = false;
    if(Map[y-1][x].pillar)ret = true;  //아래쪽에 기둥이 있으면
    if(x<n&& Map[y-1][x+1].pillar)ret= true;  //오른쪽 아래에 기둥이 있으면
    if(x>0&&x<n && Map[y][x-1].beam && Map[y][x+1].beam) ret = true;   //양 옆에 보가 있으면
    return ret;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    for(vector<int> pos : build_frame){
        int x = pos[0], y = pos[1];
        int pillar_or_beam = pos[2];
        int del_or_add = pos[3];
        if(del_or_add){//설치
            if(pillar_or_beam){//보
                if(y>0 && chk_beam(y,x,n)){
                    Map[y][x].beam=true;
                }
            }
            else{   //기둥
                if(chk_pillar(y,x)){
                    Map[y][x].pillar=true;
                }
            }
        }
        else{   //삭제
            if(pillar_or_beam){ //보
                Map[y][x].beam = false;
                for(int i=0; i<=n; i++){
                    for(int j=0; j<=n; j++){
                        if(Map[i][j].pillar) {
                            if(!chk_pillar(i,j)){
                                Map[y][x].beam = true;
                                break;
                            }
                        }
                        if(Map[i][j].beam){
                            if(!chk_beam(i,j,n)){
                                Map[y][x].beam = true;
                                break;
                            }
                        }
                    }
                }
            }
            else {  //기둥
                Map[y][x].pillar = false;
                for(int i=0; i<=n; i++){
                    for(int j=0; j<=n; j++){
                        if(Map[i][j].pillar) {
                            if(!chk_pillar(i,j)){
                                Map[y][x].pillar = true;
                                break;
                            }
                        }
                        if(Map[i][j].beam){
                            if(!chk_beam(i,j,n)){
                                Map[y][x].pillar = true;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
    for(int x=0; x<=n; x++){
        for(int y=0; y<=n; y++){
            if(Map[y][x].pillar)answer.push_back({x,y,0});
            if(Map[y][x].beam)answer.push_back({x,y,1});
        }
    }
    return answer;
}

소스코드 : Python

파이썬 풀이는 추후에 포스팅 ....