[프로그래머스] 기둥과 보 설치 (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를 한다.

 

 

 

<전체 코드>

#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;
}

 

 

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