[프로그래머스] 기둥과 보 설치

링크

https://programmers.co.kr/learn/courses/30/lessons/60061

프로그래머스

풀이

모든 명령어(기둥, 보 설치 및 삭제)를 수행한 후 구조물의 상태를 구하는 문제이다.

 

3일을 꼬박 고민해서 푼 문제이다..

처음에는 명령어를 실행할 때마다 조건을 충족하는지 확인하도록 만들 었었는데

조건을 계속 if문으로 추가 해주다 보니 나중에는 알기 어려운 코드가 되어버렸다..

 

그래서 그냥 명령어를 실행 할 때 맞는 조건이면 명령어를 실행 하는 것이 아닌 

명령어를 그냥 먼저 실행한 후 그다음에 조건을 충족하는지 확인하는 방법으로 코드를 바꿨다.

 

 

1. 명령어 그냥 실행

2. 실행되었던 명령어를 처음부터 쭉 탐색하며 조건에 충족 여부 확인

3. 실행되었던 명령어에 문제가 없다면 실행한 명령어를 그대로 실행하고 실행한 명령어에 문제가 있다면 실행한 명령어를 취소한다(추가했다면 다시 삭제, 삭제했다면 다시 추가)

 

이때 탐색하고 있는 명령어(설치된 기둥과 보)가 조건에 충족하는지 확인하기 위해서는

 

 

       1.기둥은

 검은색이 현재 놓인 기둥인데. 

첫 번째로 기둥의 y가 0일 때,

두 번째 기둥이 보의 위에 있을 때,

세 번째 기둥이 기둥 위에 있을 때,

이렇게 3가지 중 한 가지의 조건에 충족하는지 확인하면 된다.

 

 

       2.보는

 

 검은색이 현재 놓인 보인데.

첫 번째로 나의 바로 양 옆에 보가 놓여 있을 때,

두 번째로 나의 왼쪽이나 오른쪽 밑에 기둥이 있을 때,

이렇게 2가지 중 한 가지의 조건에 충족하는지 확인하면 된다.

 

 

모두 확인하고 조건에 맞게 정렬 하면 된다.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;


map<tuple<int, int, int>, int> ress;
bool cmp(vector<int> v1, vector<int> v2) {
	if (v1[0] == v2[0]) {
		if (v1[1] == v2[1]) {
			return v1[2] < v2[2];
		}
		return v1[1] < v2[1];
	}
	return v1[0] < v2[0];
}

bool check() {
	for (auto r : ress) {
		int x, y, a; tie(x, y, a) = r.first;

		if (a == 0) {//기둥
        	//기둥이 올바르게 있는제 확인
			if (y == 0 || ress.count(make_tuple( x - 1,y,1 )) || ress.count(make_tuple( x,y,1 )) || ress.count(make_tuple( x,y - 1,0 )))
				continue;
			else
				return false;
		}

		else if (a == 1) {//보
        	//보가 올바르게 있는지 확인
			if (ress.count(make_tuple( x,y - 1,0 )) || ress.count(make_tuple( x + 1,y - 1,0 )) || (ress.count(make_tuple(x - 1, y, 1)) + ress.count(make_tuple(x + 1, y, 1)) == 2))
				continue;
			else 
            	return false;
		}
	}

	return true;
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
	vector<vector<int>> answer;
	for (auto build : build_frame) {
		tuple<int, int, int> b = make_tuple( build[0],build[1],build[2] );
		int toggle = build[3];

		//명령문 그냥 실행
		if (toggle == 1) {//추가
			ress[b] = true;

			if (check() == false) {
				ress.erase(b);
			}
		}
		else if (toggle == 0) {//삭제
			ress.erase(b);

			if (check() == false) {
				ress[b] = true;
			}
		}

	}

	
	for (auto res : ress) {
		int x, y, a; tie(x, y, a) = res.first;
		vector<int> r = { x,y,a };
		answer.push_back(r);
	}
    //조건에 맞게 정렬
	sort(answer.begin(), answer.end(), cmp);

	return answer;
}