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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60061

 

특별한 함정이 없는 구현, 시뮬레이션 문제이지만 머리속으로만 그리다보니 잦은 실수가 발생하였다.

 

<전체적인 알고리즘>

1. build_frame vector의 순서대로 건물을 짓는다. 단 설치할 때 존재할 수 없는 경우에는 스킵한다.

2. 건물을 삭제하라는 명령어가 나올경우에는 우선 건물을 삭제해본다. 그리고 삭제할 때 영향을 받는 건물들만

   존재할 수 있는지 확인해본다.

3. 건물이 완성되면 (x축), (y축), (기둥, 보) 이런 순서로 3중 포문으로 vector에 저장을 한다면 굳이 sorting 하지 않아도 

   문제에서 원하는 순서대로 저장 가능하다. 

 

<건출물이 존재가능한 지 확인하는 알고리즘> -> 위 설명에서 빨간글씨에 사용하는 함수

기둥의 경우 -> 바닥위에 있거나(y가 0이거나), 

                     보의 한쪽 끝 부분 위에 있거나 (자신 왼쪽이나, 자기자신이 보를갖고있거나), 

                     다른 기둥 위에 있다면  (자신 아래쪽이 보를갖고있다면)

                     return true 를 한다.

                      

보의 경우 -> 한쪽 끝부분이 기둥 위에 있거나 (자신의 아래나, 자신의 오른쪽 아래가 기둥을 갖고 있다면)

                  양쪽 끝부분이 다른 보와 동시에 연결되어 있다면(자신의 왼쪽 이나, 자신의 오른쪽이 보를 갖고 있다면)

                  return true를 한다.

 

 

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include <string> #include <vector>   using namespace std;   bool check[102][102][2]; //0 -> 기둥 // 1-> 보 int n;   bool can_exist(int x, int y,int a)  //건축물이 존재가능한지 확인하기 {     if (a == 0)//기둥일때     {         if (y == 0)return true;    //바닥이면 가능         if ((x - 1 >= 0 && check[x - 1][y][1]) || check[x][y][1])return true;  //보의 위일 때 가능         if (check[x][y - 1][0])return true;   //다른 기둥 위일 때 가능     }     else   //보일때     {         if (y-1>=0&&check[x][y-1][0])return true; //보 왼쪽에 기둥있으면 가능         if (x+1<=n&& y - 1 >= 0&&check[x+1][y-1][0])return true; //보 오른쪽 끝에 기둥 있으면 가능         if(x-1>=0&&x+2<=n&&check[x-1][y][1] &&check[x+1][y][1])return true;//양쪽 끝 보면 가능     }     return false; } vector<vector<int>> solution(int nn, vector<vector<int>> build_frame) {           n=nn;           for (int i = 0; i < build_frame.size(); i++)     {         int x = build_frame[i][0];         int y = build_frame[i][1];         int a = build_frame[i][2];         int b = build_frame[i][3];  //삭제 0 or 설치  1           if (b == 1)//설치일 때         {             if (can_exist(x,y,a))check[x][y][a] = true;   //건축물이 존재가능하면 설치하기            }         else //삭제일 때         {             check[x][y][a] = false;//삭제 해보기             if (a == 0)  //기둥일 때                {                 //구조물이 존재하는데 존재하면 안될 때 삭제한거 취소하기                 if (x - 1 >= 0 &&y+1<=n&& check[x - 1][y+1][1] && !can_exist(x - 1, y+1, 1))check[x][y][a] = true; // 왼쪽 보                 else if(y+2<=n&&check[x][y+1][0]&&!can_exist(x,y+1,0))check[x][y][a] = true;  //위쪽 기둥                 else if (x + 1 <= n &&y+1<=n&& check[x][y+1][1] && !can_exist(x, y+1, 1))check[x][y][a] = true; //오른쪽 보                             }             else   //보일 때                 {            //if문 하나로 다 묶어도 되는데 알아보기 힘들어서 분류                 if (x - 1 >= 0 && check[x - 1][y][1] && !can_exist(x - 1, y, 1))check[x][y][a] = true; // 왼쪽 보                           else if (y + 1 <= n && check[x][y][0] && !can_exist(x, y , 0))check[x][y][a] = true;  //위쪽 기둥                 else if (x + 1 <= n && check[x + 1][y][0] && !can_exist(x + 1, y, 0))check[x][y][a] = true;  //오른쪽 기둥                 else if (x + 2 <= n && check[x + 1][y][1] &&!can_exist(x + 1, y, 1))check[x][y][a] = true;//오른쪽 보                }           }       }        vector<vector<int>> answer;     for (int i = 0; i <= n; i++)     {         for (int j = 0; j <= n; j++)         {             for (int t = 0; t < 2; t++)             {                 if (check[i][j][t])answer.push_back(vector<int>{i,j,t});             }         }     }           return answer; }

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.