2020 카카오 공채: 기둥과 보 설치

[문제 링크]

코딩테스트 연습 - 기둥과 보 설치

---

문제 접근에 따라 구현 난이도가 극심하게 달라질 수도 있다는 것을 깨닫게 해준 문제였다.

 

필자는 크기가 (n+1)X(n+1)인 board 배열을 하나 만든 다음 그 위에다 구조물을 설치하고 제거하는 식으로 구현하려했는데, 이 방법으로 구현할 경우 한 좌표에 기둥과 보가 설치되어 있는 경우를 추가로 고려해줘야하기 때문에 코드도 엄청 길어지고 디버깅하기도 쉽지 않아 한참을 고생했다.

 

단순하게 2차원 bool 배열을 2개 만들고 기둥이 설치된 정보가 담긴 배열과 보가 설치된 정보가 담긴 배열로 나눠서 관리하면 훨씬 코드도 간결하고 구현도 쉽게 할 수 있었다.

---

#include <string>
#include <vector>

using namespace std;

bool pillar[101][101];
bool bo[101][101];

bool check_pillar(int y, int x, int n)
{
	if (y == 0) return true;
	if (pillar[y - 1][x]) return true;
	if (x > 0 && bo[y][x - 1]) return true;
	if (bo[y][x]) return true;

	return false;
}

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

	return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) 
{	
	for (int i = 0; i < build_frame.size(); i++)
	{
		int xPos = build_frame[i][0];
		int yPos = build_frame[i][1];
		int isStruct = build_frame[i][2];
		int isWork = build_frame[i][3];

		if (isStruct == 0) // 기둥
		{
			if (isWork == 1) // 설치
			{
				if (check_pillar(yPos, xPos, n))
					pillar[yPos][xPos] = true;
			}

			else // 삭제
			{
				pillar[yPos][xPos] = false;

				if (yPos < n && pillar[yPos+1][xPos] && !check_pillar(yPos + 1, xPos, n))
					pillar[yPos][xPos] = true;

				else if (xPos < n && bo[yPos+1][xPos] && !check_bo(yPos + 1, xPos, n))
					pillar[yPos][xPos] = true;

				else if (xPos > 0 && bo[yPos+1][xPos-1] && !check_bo(yPos + 1, xPos - 1, n))
					pillar[yPos][xPos] = true;
			}
		}
		else // 보
		{
			if (isWork == 1) // 설치
			{
				if (check_bo(yPos, xPos, n))
					bo[yPos][xPos] = true;
			}

			else // 삭제
			{
				bo[yPos][xPos] = false;

				if (yPos < n && pillar[yPos][xPos] && !check_pillar(yPos, xPos, n))
					bo[yPos][xPos] = true;

				else if (yPos < n && xPos < n && pillar[yPos][xPos+1] && !check_pillar(yPos, xPos + 1, n))
					bo[yPos][xPos] = true;

				else if (xPos > 0 && bo[yPos][xPos-1] && !check_bo(yPos, xPos - 1, n))
					bo[yPos][xPos] = true;

				else if (xPos < n && bo[yPos][xPos+1] && !check_bo(yPos, xPos + 1, n))
					bo[yPos][xPos] = true;
			}
		}
	}

	vector<vector<int>> answer;
	
	for(int x = 0; x <= n; x++)
		for (int y = 0; y <= n; y++)
		{
			if (pillar[y][x])
				answer.push_back({ x,y,0 });

			if (bo[y][x])
				answer.push_back({ x,y,1 });
		}

	return answer;
}

알고리즘 200일 프로젝트 - 139 day