[Programmers] 기둥과 보 설치

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/60061

프로그래머스

구현력을 요구하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 build_frame 벡터를 전처리하여 설치/제거 가능 여부를 판단한 뒤 set 자료구조에 추가/삭제를 해줍니다.

1.1 저는 세로를 y, 가로를 x로 처리했고 좌상단을 0, 0으로 봤기 때문에 y를 n - frame[1]로 처리한 뒤 설치/제거 가능 여부를 판단했습니다.

2. 설치 가능 여부는 문제에서 주어진대로 구현하면 되었는데 이를 위해 visited 3차원 배열을 선언해줬습니다. 또한, build_frame 벡터는 1-index이므로 100 * 100 * 2가 아닌 101 * 101 * 2로 선언해줘야 합니다.

3. 제거 가능 여부는 해당 기둥/보를 제거했을 때, 현재 설치된 기둥/보를 다 설치할 수 있는지 여부를 판단해주면 됩니다.

4. 마지막에 answer 배열에 기둥/보를 추가할 때, 앞서 1.1에서 y를 n - y로 만들었으므로 다시 역으로 n - y로 변환한 뒤 추가해줘야 하고 문제에서 주어진 조건에 맞게 정렬을 한 뒤 반환해주면 됩니다.

 

	#include <string>
	#include <vector>
	#include <set>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	const int MAX = 100 + 1;
	bool visited[MAX][MAX][2]; // 0: 기둥, 1: 보
	struct State
	{
	int y, x, a;
	};
	bool operator<(State a, State b)
	{
	return a.y != b.y ? a.y < b.y : (a.x != b.x ? a.x < b.x : a.a < b.a);
	}
	bool cmp(State a, State b)
	{
	if (a.y == b.y)
	{
	if (a.x == b.x)
	{
	return a.a < b.a;
	}
	return a.x < b.x;
	}
	return a.y < b.y;
	}
	set<State> s;
	bool canBeInstalled(int y, int x, int a, int n)
	{
	if (visited[y + 1][x][0])
	{
	return true;
	}
	if (a == 0)
	{
	if (y == n)
	{
	return true;
	}
	if (visited[y][x][1])
	{
	return true;
	}
	if (x >= 1 && visited[y][x - 1][1])
	{
	return true;
	}
	}
	else
	{
	if (visited[y][x - 1][1] && visited[y][x + 1][1])
	{
	return true;
	}
	if (x + 1 <= n && visited[y + 1][x + 1][0])
	{
	return true;
	}
	}
	return false;
	}
	bool canBeDeleted(int y, int x, int a, int n)
	{
	visited[y][x][a] = false;
	for (auto state : s)
	{
	if (y == state.y && x == state.x && a == state.a)
	{
	continue;
	}
	if (!canBeInstalled(state.y, state.x, state.a, n))
	{
	visited[y][x][a] = true;
	return false;
	}
	}
	return true;
	}
	vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
	for (vector<int> frame : build_frame)
	{
	int y = n - frame[1];
	int x = frame[0];
	int a = frame[2];
	int b = frame[3];
	if (b == 1)
	{
	if (canBeInstalled(y, x, a, n))
	{
	s.insert({y, x, a});
	visited[y][x][a] = true;
	}
	}
	else
	{
	if (canBeDeleted(y, x, a, n))
	{
	s.erase({y, x, a});
	}
	}
	}
	vector<vector<int>> answer;
	for (auto state : s)
	{
	vector<int> v{state.x, n - state.y, state.a};
	answer.push_back(v);
	}
	sort(answer.begin(), answer.end());
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~