[C++] 백준 14500 테트로미노

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

14500번: 테트로미노

#include <iostream>
#include <algorithm>

using namespace std;
int N, M;
int arr[500][500] = {0};
bool was_thr[500][500] = {false};
int dfs(int x, int y, int val, int cnt)
{
	enum dir {R, L, D, U, NOD};
	int result = 0;
	constexpr int d_x[4] = {0, 0, 1, -1};
	constexpr int d_y[4] = {1, -1, 0, 0};
	for(int d = 0; d < NOD; ++d)
	{
		const int now_x = x + d_x[d];
		const int now_y = y + d_y[d];
		if(was_thr[now_x][now_y]) continue;
		if(now_x < 0 || now_x >= N || now_y < 0 || now_y >= M) continue;
		int value = val + arr[now_x][now_y];
		if(cnt + 1 < 4)
		{
			was_thr[now_x][now_y] = true;
			value = dfs(now_x, now_y, value, cnt + 1);
			was_thr[now_x][now_y] = false;
		}
		result = max<int>(result, value);
	}
	return result;
}

bool is_valid(int input, int max)
{
	return input >= 0 && input < max;
}

int check_fword(int x, int y)
{
	int result = 0;
	int case_x[8][4] = {{0, 1, 1, 2}, {0, 1, 1, 2}, {0, 0, 1, 0}, {0, 0, -1, 0},
						{0, -1, -1, -2}, {0, -1, -1, -2}, {0, 0, 1, 0}, {0, 0, -1, 0}};
	int case_y[8][4] = {{0, 0, -1, 0}, {0, 0, 1, 0}, {0, 1, 1, 2}, {0, 1, 1, 2},
						{0, 0, -1, 0}, {0, 0, 1, 0}, {0, -1, -1, -2}, {0, -1, -1, -2}};
	for(int i = 0; i < 8; ++i)
	{
		int x_0 = case_x[i][0] + x;
		int x_1 = case_x[i][1] + x;
		int x_2 = case_x[i][2] + x;
		int x_3 = case_x[i][3] + x;
		int y_0 = case_y[i][0] + y;
		int y_1 = case_y[i][1] + y;
		int y_2 = case_y[i][2] + y;
		int y_3 = case_y[i][3] + y;
		if ( is_valid(x_0, N) && is_valid(x_1, N) && is_valid(x_2, N) && is_valid(x_3, N) &&
			is_valid(y_0, M) && is_valid(y_1, M) && is_valid(y_2, M) && is_valid(y_3, M))
		{
			int ret = arr[x_0][y_0] + arr[x_1][y_1] + arr[x_2][y_2] + arr[x_3][y_3];
			result = result > ret ? result : ret;
		}
	}
	return result;
}

int main(int argc, char **argv)
{
	cin >> N >> M;
	int answer = 0;
	for(int i = 0; i < N; ++i)
	{
		for(int j = 0; j < M; ++j)
		{
			cin >> arr[i][j];
		}
	}

	for(int i = 0; i < N; ++i)
	{
		for(int j = 0; j < M; ++j)
		{
			was_thr[i][j] = true;
			answer = max<int>({dfs(i, j, arr[i][j], 1), check_fword(i, j), answer});
			was_thr[i][j] = false;
		}
	}
	cout << answer;
	return 0;
}

 

문제 유형 : DFS, 브루트 포스, 구현
소모 시간 : 약 5시간 (2일 동안 3시간 + 2시간)

 

 해당 문제는 전체 탐색 및 일부 예외처리를 통해 문제를 풀 수 있다.

 

2시간 정도 문제를 풀다가 도저히 구현 방법이 떠오르지 않아 다른 블로그를 많이 참고했는데,

그 중에서 조금 놀랄 만한 내용이 있었다.

위 그림은 테트로미노에서 나올 수 있는 도형 예시인데,

예외케이스인 ㅗ 도형을 제외한 나머지는 중복 없이 DFS 로 4칸 이동하면 나오는 도형이라는 점

 

이런 점을 보고나서 귀찮아서 2시간 정도 다른 블로그 내용을 옮겨적다가 안되서

다음 날에 되어서 차분히 정리하고 풀어보니 다행히도 풀렸다.

 

해당 문제의 핵심은 도형의 모형에서 DFS를 유추할 수 있는가? 인 것 같다.

진짜 코딩 잘하는 사람들은 저런 걸 잘 파악하는 가보다.

그저 신기할 따름

 

구현

DFS 와 도형 간의 상관 관계를 파악했다면 구현은 그렇게 어렵지 않다.

 

1. 0,0 부터 N-1, M-1 까지 모두 서치할 수 있도록 구현 (이중 for문)

2. 시작 지점에서 4칸을 DFS로 Search 할 수 있도록 구현

3. 이전에 들렀던 칸을 다시 방문하지 않도록 예외처리 구현

4. ㅗ 도형 예외처리 구현

5, 탐색 결과 중 최대 값을 저장해 출력

 

시행착오

문제 접근 과정에서 DFS, 테트로미노 간 상관 관계를 찾지 못하고 브루트 포스만 생각하고 있었다.

다음 번에 이런 문제를 풀 때는 기존에 내가 알고있던 알고리즘과 문제의 상관 관계를 찾는 데에 좀 더 힘을 써야 할 듯