Byung Wook Park (박병욱)

Byung Wook Park (박병욱)

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

✔️ 문제

✔️ 문제 이해

  • 죠르디는 2차원 가상 벽면에 기둥과 보를 설치하는 로봇의 동작을 시뮬레이션 하는 프로그램을 만들고 있다.
  • 죠르디를 도와 프로그램을 만들어야 한다.
  • 기둥과 보는 아래와 같은 조건이 있다.
    • 기둥 : 바닥위에 있거나, 보의 한쪽 끝 부분 위에 있거나, 다른 기둥 위에 있어야 한다.
    • 보 : 한쪽 끝 부분이 기둥 위에 있거나, 양쪽 끝 부분이 다른 보와 동시에 연결돼야 한다.
  • 2차원 벽면은 n x n 정사각 격자 형태이다. 각 격자는 1 x 1 크키이다.
  • 벽면의 크기 n과 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 주어진다.
    • 작업(build_frame) [x, y, a, b] 형태로 주어진다.
    • x, y 는 좌표이고, a는 기둥(0) or 보(1), b는 설치(1) or 삭제(0)
  • 기둥과 보의 조건에 부합하는 작업을 모두 수행하고 구조물들의 최종 결과를 반환해야 한다.
  • 구조물들의 최종 결과는 [x, y, a] 형태로 반환한다. x, y, a 순으로 정렬이 돼있어야 한다.
  • 값 범위
    • 5 <= n <= 100
    • 1<= build_frame의 세로 길이 <= 1000

✔️ 알고리즘 설계

  1. 주어진 작업을 하나씩 수행하고 결과를 반환한다.

    1-1. 작업을 먼저 수행하고, 벽면의 모든 기둥과 보에 대해서 조건 검사를 한다.

    1-2. 수행된 작업이 조건 위배를 유발한다면, 작업을 하기전 상태로 되돌린다.

✔️ 상세 구현설명

  • 기둥과 보를 2차원 배열에 설치하는 방식으로 구현한다.
  • 문제에서 주어지는 좌표는 데카르트 좌표계다. 이를 2차원 배열 기준 좌표계로 변환 해준다.
  • 변환된 2차원 배열 좌표계와 a, b를 사용해서 기둥 or 보를 건설한다.
  • 기둥과 보는 같은 위치에 올 수 있으므로 정보를 각각 다른 2차원 배열에 저장한다.
  • 문제에서 주어진 기둥 or 보의 조건을 검사하고, 조건을 위배하면 원상복구한다. (해당 작업 무시)
  • 모든 작업 수행후 기둥과 보 정보가 저장된 2차원 배열을 조회하여 최종 결과를 벡터에 저장한다.
  • 문제 조건에 따라 x, y, a 순으로 정렬해서 반환한다.
  • 참고로 기둥과 보는 같은 위치에 올 수 있다.

👨🏻‍💻 소스 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool pillar[101][101]; // 기둥 정보를 저장할 2차원 배열.
bool barrage[101][101]; // 보 정보를 저장할 2차원 배열.
int N;

bool check() {

	for (int i = 0; i <= N; i++) { // 보 조건 검사.
		for (int j = 0; j <= N; j++) {
			if (barrage[i][j]) {
				// 보의 한 쪽 끝 부분이 기둥 위에 있는 경우.
				if (pillar[i + 1][j] || pillar[i + 1][j + 1]) continue; 
				// 보의 양쪽 끝 부분이 동시에 다른 보와 연결돼있는 경우.
				if (barrage[i][j - 1] && barrage[i][j + 1]) continue; 
				return false;
			}
		}
	}

	for (int i = 0; i <= N; i++) { // 기둥 조건 검사.
		for (int j = 0; j <= N; j++) {
			if (pillar[i][j]) {
				if (i == N) continue; // 기둥이 바닥에 있는 경우.
				if (pillar[i + 1][j]) continue;// 기둥이 다른 기둥 위에 있는 경우.
				// 기둥이 보 왼쪽 또는 오른쪽 끝 위에 있는 경우.
				if (barrage[i][j] || barrage[i][j - 1]) continue; 
				return false;
			}
		}
	}

	return true;
}

void build(int x, int y, bool structure, bool action) {

	if (structure)
		barrage[x][y] = action; // 설치 or 삭제.
	else
		pillar[x][y] = action;

	if (!check()) { // 작업의 결과가 조건을 위배하면, 원상 복구.
		if (structure)
			barrage[x][y] = !action;
		else
			pillar[x][y] = !action;
	}
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
	vector<vector<int>> answer;
	N = n;

	for (int i = 0; i < build_frame.size(); i++) {
		int x = N - build_frame[i][1]; // 행렬 기준 좌표계로 변환.
		int y = build_frame[i][0];
		int a = build_frame[i][2];
		int b = build_frame[i][3];

		build(x, y, a, b); // 기둥과 보 건설을 시도한다.
	}

	// 모든 작업이 끝난 후 구조물들의 최종 결과를 저장한다.
	for (int i = 0; i <= N; i++) {  
		for (int j = 0; j <= N; j++) {

			int x = j, y = N - i; // 처음에 주어진 데카르트 좌표계로 변환.

			if (pillar[i][j]) { // 기둥 정보 저장.
				answer.push_back({ x,y,0 });
			}

			if (barrage[i][j]) { // 보 정보 저장.
				answer.push_back({ x,y,1 });
			}
            
		}
	}

	sort(answer.begin(), answer.end()); // 문제 조건에 맞추어 정렬 수행.
	return answer;
}

✔️ 문제 회고

  • 특별한 알고리즘을 요구하지 않는 문제다. 복잡한 문제를 코드로 풀어내는 능력이 필요했다.
  • 코드를 최대한 간결하게 짜기위해 리팩토링을 진행하며 문제를 풀었다. (build 함수는 원래 3~4배 정도 길었다.)
  • 2차원 배열을 활용했다. 기둥과 보는 격자선의 교차점을 기준으로 설치된다. 각 교차점의 위치를 배열로 생각해서 풀면 편하다.
  • 주어진 좌표는 우리가 흔히 수학 시간에 사용했던 데카르트 좌표 이므로 이를 2차원 배열 기준 좌표로 변환하는 작업이 필요했다. 복잡할 수 있지만 조금만 생각해보면 된다.
  • 처음에 같은 반복문 속에서 기둥을 검사한 다음 보의 조건 검사를 했는데, 기둥 검사 부분에서 continue가 걸리면 보에 대한 조건 검사가 이루어지지 않는다.
  • 문제를 이해하고 코딩으로 풀어내는 능력이 많이 요구됐다. 연습이 더 필요하다.