[2020카카오공채] 기둥과 보 설치

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

프로그래머스

 

노트에 풀이를 정리한 후 풀었더니 훨씬 쉽고 빠르게 풀었다!

복잡한 문제일수록 꼭 먼저 정리한 후 구현하는 습관을 들이자

 

문제가 길기 때문에 모든 요구사항을 잘 정리한 후 풀어야 한다.

 

내가 푼 방법은

기둥과 보의 위치를 저장하는 2차원 배열 gi[101], bo[101]을 선언한 후

설치나 삭제를 할 때마다 배열의 내용을 검사해가며 풀었다.

 

현재 위치에 기둥과 보를 설치할 수 있는지 검사하는 check_gi, check_bo 함수를 따로 만들어서 사용했는데

설치 뿐만 아니라 삭제할 때에도 두 함수를 사용했다.

 

삭제를 할 때 일단 삭제를 했다 치고 배열에 0을 넣어놓고

영향을 받는 기둥과 보에 대해 check_gi, check_bo를 사용해서 검사한 후,

false가 반환되면 삭제가 불가능하다는 뜻이므로 다시 배열에 1을 넣어준다.

물론 true가 반환되면 그대로 삭제처리하면 된다.

 

설치, 삭제 작업이 모두 끝난 후에는

gi, bo 배열을 탐색하며 answer에 값을 넣어준 뒤 반환하면 끝!

 

#include <vector>

using namespace std;

bool gi[101][101] = {};
bool bo[101][101] = {};

bool check_gi(int x, int y, int n) {
    if (y == 0) return 1;
    if (gi[x][y - 1]) return 1;
    if (x > 0 && bo[x - 1][y]) return 1;
    if (x < n && bo[x][y]) return 1;

    return 0;
}

bool check_bo(int x, int y, int n) {
    if (gi[x][y - 1]) return 1;
    if (x < n && gi[x + 1][y - 1]) return 1;
    if (x > 0 && x < n && bo[x + 1][y] && bo[x - 1][y]) return 1;

    return 0;
}

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

    for (int i = 0; i < build_frame.size(); i++) {
        int x, y, a, b;
        x = build_frame[i][0];
        y = build_frame[i][1];
        a = build_frame[i][2];
        b = build_frame[i][3];

        // 기둥 설치
        if (a == 0 && b == 1) {
            if (check_gi(x, y, n)) {
                gi[x][y] = 1;
            }
        }
        // 보 설치
        else if (a == 1 && b == 1) {
            if (check_bo(x, y, n)) {
                bo[x][y] = 1;
            }
        }
        // 기둥 삭제
        else if (a == 0 && b == 0) {
            bool can = 1;
            gi[x][y] = 0;

            if (y < n && gi[x][y + 1] && !check_gi(x, y + 1, n)) can = 0;
            else if (y < n && bo[x][y + 1] && !check_bo(x, y + 1, n)) can = 0;
            else if (x > 0 && bo[x - 1][y + 1] && y < n && !check_bo(x - 1, y + 1, n)) can = 0;

            if (!can) gi[x][y] = 1;
        }
        // 보 삭제
        else if (a == 1 && b == 0) {
            bool can = 1;
            bo[x][y] = 0;

            if (gi[x][y] && !check_gi(x, y, n)) can = 0;
            else if (x < n && gi[x + 1][y] && !check_gi(x + 1, y, n)) can = 0;
            else if (x > 0 && bo[x - 1][y] && !check_bo(x - 1, y, n)) can = 0;
            else if (x < n && bo[x + 1][y] && !check_bo(x + 1, y, n)) can = 0;

            if (!can) bo[x][y] = 1;
        }
    }

    // answer에 기둥과 보 상태 넣기
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (gi[i][j]) {
                answer.push_back({ i, j, 0 });
            }
            if (bo[i][j]) {
                answer.push_back({ i, j, 1 });
            }
        }
    }

    return answer;
}

 

---

 

위의 코드에서 x좌표나 y좌표를 더하거나 빼는 경우, -1 같이 유효하지 않은 배열 인덱스를 참조하는 경우를 막기 위해 일일히 if문 안에 x, y에 대한 범위 조건을 넣어주었는데

다른 사람들 코드를 보니 아예 배열의 모서리를 비워주는 방식으로 구현한게 있어서 따라해보았다.

 

단, 이 방법으로 구현하기 위해서는 마지막에 answer에 값을 넣어줄 때 좌표값에서 1을 빼 주어야 한다.

 

#include <vector>

using namespace std;

bool gi[102][102] = {};
bool bo[102][102] = {};

bool check_gi(int x, int y) {
	if (y == 1) return 1;
	if (gi[x][y - 1]) return 1;
	if (bo[x - 1][y]) return 1;
	if (bo[x][y]) return 1;

	return 0;
}

bool check_bo(int x, int y) {
	if (gi[x][y - 1]) return 1;
	if (gi[x + 1][y - 1]) return 1;
	if (bo[x + 1][y] && bo[x - 1][y]) return 1;

	return 0;
}

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

	for (int i = 0; i < build_frame.size(); i++) {
		int x, y, a, b;
		x = build_frame[i][0];
		y = build_frame[i][1];
		a = build_frame[i][2];
		b = build_frame[i][3];
		x++;
		y++;

		// 기둥 설치
		if (a == 0 && b == 1) {
			if (check_gi(x, y)) {
				gi[x][y] = 1;
			}
		}
		// 보 설치
		else if (a == 1 && b == 1) {
			if (check_bo(x, y)) {
				bo[x][y] = 1;
			}
		}
		// 기둥 삭제
		else if (a == 0 && b == 0) {
			bool can = 1;
			gi[x][y] = 0;

			if (gi[x][y + 1] && !check_gi(x, y + 1)) can = 0;
			else if (bo[x][y + 1] && !check_bo(x, y + 1)) can = 0;
			else if (bo[x - 1][y + 1] && y < n && !check_bo(x - 1, y + 1)) can = 0;

			if (!can) gi[x][y] = 1;
		}
		// 보 삭제
		else if (a == 1 && b == 0) {
			bool can = 1;
			bo[x][y] = 0;

			if (gi[x][y] && !check_gi(x, y)) can = 0;
			else if (gi[x + 1][y] && !check_gi(x + 1, y)) can = 0;
			else if (bo[x - 1][y] && !check_bo(x - 1, y)) can = 0;
			else if (bo[x + 1][y] && !check_bo(x + 1, y)) can = 0;

			if (!can) bo[x][y] = 1;
		}
	}

	// answer에 기둥과 보 상태 넣기
	for (int i = 1; i <= n + 1; i++) {
		for (int j = 1; j <= n + 1; j++) {
			if (gi[i][j]) {
				answer.push_back({ i - 1, j - 1, 0 });
			}
			if (bo[i][j]) {
				answer.push_back({ i - 1, j - 1, 1 });
			}
		}
	}

	return answer;
}