[BOJ] 14500번 테트로미노(C++)

풀이 소요시간 : 60분 초과

나는 아직 멀었다는 것을 느꼈다. 요즘 실력이 조금 올랐다고 내심 조금은 자만하고있었는데, 항상 긴장하고 준비해야겠다. 처음 이 문제를 접했을 때 완전한 깡구현 말고는 풀이 방법이 없다고 생각했다. 따라서 모든 방향배열을 준비했고, 이 과정에 논리적인 문제는 없었지만 정말 이게 맞나 하는 생각이 들 수 밖에 없었다.

요즘들어 최대한 많은 유형의 접근방식을 알아둬야겠다는 생각을 하고있었고, 일정 시간 뒤에 망설임 없이 정석 풀이를 참고한 결과 역시나 비교적 깔끔한 풀이과정은 존재했다.

놀랍게도 ㅗ 모양의 테트로미노를 제외한 나머지 4개의 테트로미노가 가진 경우의 수는 원점으로부터 깊이가 4인 DFS의 자취와 같았다는 것이다. 내가 이것을 실전에서 떠올릴 수 있었을까? 불가능하다. 모르는 접근방식이 나왔으니 다행으로 여기자.

4개의 테트로미노를 DFS 로 처리하고, 나머지 하나의 테트로미노는 따로 처리해주면 문제는 해결된다.

전체 코드

#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

int N, M;
int Map[501][501];
int Visit[501][501];
int Ans = 0;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };


void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> Map[i][j];
		}
	}
}

void Dfs(int x, int y, int Count, int Sum) {
	if (Count == 3)
	{
		Ans = max(Ans, Sum);
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
		if (Visit[nx][ny] == 1) continue;

		Visit[nx][ny] = 1;
		Dfs(nx, ny, Count + 1, Sum + Map[nx][ny]);
		Visit[nx][ny] = 0;
	}
}

int main() {
	Input();
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			Visit[i][j] = 1;
			Dfs(i, j, 0, Map[i][j]);
			Visit[i][j] = 0;

			if (i - 1 >= 1 && i + 1 <= N && j + 1 <= M) Ans = max(Ans, Map[i][j] + Map[i + 1][j] + Map[i - 1][j] + Map[i][j + 1]);
			if (i - 1 >= 1 && i + 1 <= N && j - 1 >= 1) Ans = max(Ans, Map[i][j] + Map[i + 1][j] + Map[i - 1][j] + Map[i][j - 1]);
			if (j - 1 >= 1 && j + 1 <= M && i - 1 >= 1) Ans = max(Ans, Map[i][j] + Map[i][j - 1] + Map[i][j + 1] + Map[i - 1][j]);
			if (j - 1 >= 1 && j + 1 <= M && i + 1 <= N) Ans = max(Ans, Map[i][j] + Map[i][j - 1] + Map[i][j + 1] + Map[i + 1][j]);
		}
	}
	cout << Ans;
}