[백준알고리즘] 2339번: 석판 자르기-C++

2339번: 석판 자르기 (acmicpc.net)

2339번: 석판 자르기

이번 문제도 분할 정복 방식이다. 사실 문제를 처음 보자마자 아이디어는 떠올랐다. 그런데, 분할할 때마다 조건을 검사하는 과정에서 조각난 석판을 반복해서 검사하는 게 시간이 많이 소요될 것 같았다. 그래서 어떤 방식으로 처리를 해야 할지 고민하느라 시간을 많이 소요했다. 그래서 시간을 많이 소요하지 않게 하기 위한 방법을 고민하다 보니 메모리가 걸렸다.

결국에는 일일이 조건을 검사해도 시간이 여유로운 편이었다. 이래서 시간 복잡도를 미리 생각해두는 게 중요한 것 같다. 머리가 나빠 머리를 더 고생시켰다.

---

문제 풀이

문제 자체는 간단한 아이디어로 풀 수 있다.

• 주어진 석판 조각에서 불순물을 찾는다.
• 불순물에서 세로 방향 또는 가로 방향으로 자를 수 있는지 검사한다.
• 나뉜 두 조각에서 각각 재귀적으로 나눌 수 있는 방법의 수를 구한다.
• 두 조각에서 구한 나눌 수 있는 방법의 수를 곱한다.

 

기본적인 아이디어는 위의 방법으로 진행하면 된다. 여기서 추가적으로 조건들을 붙이고 개선하면 됐다.

 

처음에 놓쳤던 조건만 말하자면, 가장 끝의 라인을 자르는 경우다. 이 경우에는 자른 뒤에 조각이 하나만 나오는 것과 같다. 아래와 같은 조각이 있을 때의 것이다.

2 0
0 1

위의 경우에는 자를 수 있는 경우로 봤었다. 하지만, 위의 경우는 결국 아래의 경우와 같다. 나눌 수 없는 조각인 것이다.

2 0 0
0 1 0
0 0 0

위의 경우는 나눠도 반대쪽 조각에는 보석이 없기 때문에 나눌 수 없다.

 

그리고, 애초에 문제에서도 조건이 있었다..

문제를 잘 읽도록 하자.

 

다른 세부 조건들은 코드를 보면 쉽게 확인할 수 있을 것이다.

 

코드는 더 정리할 수 있을텐데, 함수가 계속 많아지는 게.. 이 문제를 풀면서 그렇게까지 나눠야 하나 싶어서 멈췄다. 마음에 안 드는 부분들이 남아있긴 한데 말이다.

이렇게 코드를 올리면 블로그에서는 보기 힘들 것 같지만, 코드를 복사해 가서 함수 선언/호출 부분들을 이동해가면서 보면 쉽게 볼 수 있을 거라 생각한다.

#include <cstdio>
#include <map>

enum DIRECTION_e {
	DIRECTION_VERTICAL,
	DIRECTION_HORIZONTAL,
};

struct POINT_st {
	POINT_st(int y, int x) : y(y), x(x) {};

	int y;
	int x;
};

typedef std::pair<int, int> pairDirtGem; //< 불순물:보석 쌍

int inputSideLength();
void inputMatrix(const int len);
pairDirtGem getDirtGem(const POINT_st &start, const POINT_st &end);
bool isCompletePiece(const pairDirtGem &pieceState);
bool isCompletePiece(const POINT_st &start, const POINT_st &end);
bool isErrorPiece(const pairDirtGem &pieceState);
int calculateCuttableWays(const POINT_st &start, const POINT_st &end, const DIRECTION_e direction);

int map[21][21];

int main(void) {
	const int len = inputSideLength();
	inputMatrix(len);

	const POINT_st start(0, 0);
	const POINT_st end(len, len);

	if ( true == isCompletePiece(start, end) ) {
		printf("1");
	}
	else {
		const int waysStartWithVertical = calculateCuttableWays(start, end, DIRECTION_VERTICAL);
		const int waysStartWithHorizontal = calculateCuttableWays(start, end, DIRECTION_HORIZONTAL);

		const int ways = waysStartWithVertical + waysStartWithHorizontal;
		if ( 0 == ways ) {
			printf("-1");
		}
		else {
			printf("%d", ways);
		}
	}

	return 0;
}

int inputSideLength() {
	int N;
	scanf("%d", &N);
	return N;
}

void inputMatrix(const int len) {
	for ( int y = 0; y < len; ++y ) {
		for ( int x = 0; x < len; ++x ) {
			::scanf("%d", &map[y][x]);
		}
	}
}

pairDirtGem getDirtGem(const POINT_st &start, const POINT_st &end) {
	int dirt = 0;
	int gem = 0;

	for ( int y = start.y; y < end.y; ++y ) {
		for ( int x = start.x; x < end.x; ++x ) {
			if ( 1 == map[y][x] ) {
				++dirt;
			}
			else if ( 2 == map[y][x] ) {
				++gem;
			}
		}
	}

	return std::make_pair(dirt, gem);
}

bool isCompletePiece(const pairDirtGem &pieceState) {
	const int &dirt = pieceState.first;
	const int &gem = pieceState.second;

	if ( 0 == dirt && 1 == gem ) {
		return true;
	}

	return false;
}

bool isCompletePiece(const POINT_st &start, const POINT_st &end) {
	const pairDirtGem pieceState = getDirtGem(start, end);
	return isCompletePiece(pieceState);
}

bool isErrorPiece(const pairDirtGem &pieceState) {
	const int &dirt = pieceState.first;
	const int &gem = pieceState.second;

	if ( 0 == dirt && 1 < gem ) {
		return true;
	}
	else if ( 0 == gem ) {
		return true;
	}
	else if ( 1 == dirt && 1 == gem ) { //< 불순물과 보석이 하나씩 있으면, 나누었을 때 최소한 한쪽 면은 보석이 없음
		return true;
	}

	return false;
}

bool isCuttable(const POINT_st &start, const POINT_st &end, const POINT_st &cutPoint, const DIRECTION_e direction) {
	switch ( direction ) {
	case DIRECTION_VERTICAL:
		if ( cutPoint.x == start.x || cutPoint.x == end.x ) {
			return false;
		}

		for ( int y = start.y; y < end.y; ++y ) {
			if ( 2 == map[y][cutPoint.x] ) {
				return false;
			}
		}
		break;

	case DIRECTION_HORIZONTAL:
		if ( cutPoint.y == start.y || cutPoint.y == end.y ) {
			return false;
		}

		for ( int x = start.x; x < end.x; ++x ) {
			if ( 2 == map[cutPoint.y][x] ) {
				return false;
			}
		}
		break;

	default:
		break;
	}

	return true;
}

int calculateCuttableWays(const POINT_st &start, const POINT_st &end, const DIRECTION_e direction) {
	const pairDirtGem pieceState = getDirtGem(start, end);
	if ( true == isCompletePiece(pieceState) ) {
		return 1;
	}
	else if ( true == isErrorPiece(pieceState) ) {
		return 0;
	}

	int ways = 0;
	for ( int y = start.y; y < end.y; ++y ) {
		for ( int x = start.x; x < end.x; ++x ) {
			if ( 1 != map[y][x] ) {
				continue;
			}

			const POINT_st currentPoint(y, x);

			switch ( direction ) {
			case DIRECTION_VERTICAL: {
				if ( false == isCuttable(start, end, currentPoint, DIRECTION_VERTICAL) ) {
					continue;
				}

				int leftWays = calculateCuttableWays(start, POINT_st(end.y, x), DIRECTION_HORIZONTAL);
				if ( 0 == leftWays ) {
					continue;
				}
				int rightWays = calculateCuttableWays(POINT_st(start.y, x + 1), end, DIRECTION_HORIZONTAL);
				if ( 0 == rightWays ) {
					continue;
				}

				ways += (leftWays * rightWays);
			} break;

			case DIRECTION_HORIZONTAL: {
				if ( false == isCuttable(start, end, currentPoint, DIRECTION_HORIZONTAL) ) {
					continue;
				}

				int upWays = calculateCuttableWays(start, POINT_st(y, end.x), DIRECTION_VERTICAL);
				if ( 0 == upWays ) {
					continue;
				}
				int downWays = calculateCuttableWays(POINT_st(y + 1, start.x), end, DIRECTION_VERTICAL);
				if ( 0 == downWays ) {
					continue;
				}

				ways += (upWays * downWays);
			} break;

			default:
				break;
			}
		}
	}
	return ways;
}