[Baekjoon] 14500번: 테트로미노

 

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

---

 

문제 해결 과정

착안

표현 가능한 테트로미노의 경우의 수는 아래의 그림과 같이 총 19 가지이므로, 이에 대한 경우의 수를 모두 계산해봄으로써 문제를 해결하고자 하였다.

DFS로 표현 가능한 경우(파란색 표시) 15 가지와 DFS로 표현이 불가능한 경우(빨간색 표시) 4 가지

 

위와 같이 매우 다양한 테트로미노 케이스에 대해 일일이 계산하는 함수를 작성하여 문제를 해결하는 것은 비효율적이라고 판단하였다. 따라서, 어느 정도의 중복 계산을 허용하기로 하고 깊이 우선 탐색(depth-first search)을 통해 테트로미노를 탐색한 다음, 깊이 우선 탐색을 통해 구현이 불가능한 경우의 테트로미노에 대해서만 별도로 직접 계산하는 방식으로 문제를 해결하고자 했다.

 

깊이 우선 탐색을 통해 계산을 하는 경우, 시작점을 기준으로 하여 가능한 모양의 테트로미노를 탐색할 때, 중복된 계산을 최대한 줄이는 것이 관건이라고 생각하였다. 이에 따라 오른쪽, 아래쪽, 왼쪽으로만 깊이 우선 탐색을 수행하도록 구현하고자 하였다. 이와 같이 프로그래밍하면, 2 가지 형태의 테트로미노(가로 방향 막대 모양, 정사각형 모양)만 중복하여 계산되기 때문에 시간 복잡도 상에 큰 문제가 되지는 않을 거라고 판단하여 그냥 중복계산을 허용하고자 했다.

 

구현

위에서 설명한 것과 같이 깊이 우선 탐색을 수행함에 있어서, 중복 계산을 줄이기 위해 위쪽 방향으로는 탐색을 수행하지 않도록 구현하였으며 깊이 우선 탐색으로 표현되지 않는 경우에 대해서는 직접 계산을 통해 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int N, M;
int Paper[500][500];
bool Visited[500][500];
int Max, Sum, Count;

void FindByDFS(int x, int y)
{
	if (Visited[y][x])
		return;

	int value = Paper[y][x];
	Visited[y][x] = true;
	Sum += value;
	Count++;

	if (Count == 4)
	{
		Max = Sum > Max ? Sum : Max;
		Visited[y][x] = false;
		Sum -= value;
		Count--;
		return;
	}

	if (x < M - 1)	FindByDFS(x + 1, y);
	if (y < N - 1)	FindByDFS(x, y + 1);
	if (x > 0)		FindByDFS(x - 1, y);

	Visited[y][x] = false;
	Sum -= value;
	Count--;
}

void ExceptionCases(int x, int y)
{
	if (x < M - 2)
	{
		int temp = Paper[y][x] + Paper[y][x + 1] + Paper[y][x + 2];
		if (y > 0)		Max = temp + Paper[y - 1][x + 1] > Max ? temp + Paper[y - 1][x + 1] : Max;
		if (y < N - 1)	Max = temp + Paper[y + 1][x + 1] > Max ? temp + Paper[y + 1][x + 1] : Max;
	}

	if (y < N - 2)
	{
		int temp = Paper[y][x] + Paper[y + 1][x] + Paper[y + 2][x];
		if (x > 0)		Max = temp + Paper[y + 1][x - 1] > Max ? temp + Paper[y + 1][x - 1] : Max;
		if (x < M - 1)	Max = temp + Paper[y + 1][x + 1] > Max ? temp + Paper[y + 1][x + 1] : Max;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> Paper[i][j];

	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
		{
			FindByDFS(x, y);
			ExceptionCases(x, y);
		}

	cout << Max << "\n";
	return 0;
}

 

실행 결과

* 함수 이름 변경으로 인해 코드 길이만 변경됨.