[BOJ] 14500 : 테트로미노 - travelbeeee

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

---

[ 알고리즘풀이 ]

 기본적으로, Input이 작으므로 2차원 배열에 테트로미노를 넣을 수 있는 모든 경우에 대해서 구해보면 된다. 하지만, 테트로미노의 종류가 5개나 되고 회전과 대칭을 하는 경우를 추가적으로 고려해보면 모든 경우에 대해서 구해보기가 생각보다 어렵다는 것을 알 수 있다.

 

 하지만, DFS 를 이용하면 대부분의 경우에 대해서 쉽게 구할 수 있다.

 2차원 배열의 한 지점에서 DFS를 통해 갈 수 있는 길이가 4인 모든 경로를 생각해보자.

 위의 그림과 같이 4가지 경로가 존재하고, 이 경로들을 회전하거나 대칭한 다른 경로들이 존재한다.

 즉, 5가지의 테트로미노 중 아래 그림을 제외하고 다른 테트로미노의 경우의 수는 그 지점에서 길이가 4인 DFS 탐색을 진행하는 것과 같다.

 따라서, 모든 지점에서 길이가 4가 될 때까지 DFS 탐색을 진행하고 위의 테트로미노만 따로 빼서 모든 경우에 대해서 계산해보면 답을 구할 수 있다. 위의 테트로미노도 가로로 눕힌 경우와 세로로 눕힌 경우로 나눠서 함수를 구현하면 더 편하게 해결할 수 있다.

#include<iostream>
#include<algorithm>

using namespace std;

int map[500][500] = {};
int N, M, ansSum = -999999999;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
bool visited[500][500] = {};

void DFS(int r, int c, int count, int sum) {
	if (count == 4){
		ansSum = max(ansSum, sum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nextR = r + dx[i], nextC = c + dy[i];
		if (!(0 <= nextR && nextR < N && 0 <= nextC && nextC < M))
			continue;
		if (visited[nextR][nextC] != true) {
			visited[nextR][nextC] = true;
			DFS(nextR, nextC, count + 1, sum + map[nextR][nextC]);
			visited[nextR][nextC] = false;
		}
	}
}

void getTetromino1() {
	for (int i = 0; i < N - 2; i++) {
		for (int j = 0; j < M; j++) {
			int sum = map[i][j] + map[i + 1][j] + map[i + 2][j];
			if (j < N - 1)
				ansSum = max(ansSum, sum + map[i + 1][j + 1]);
			if (0 < j)
				ansSum = max(ansSum, sum + map[i + 1][j - 1]);
		}
	}
	return;
}

void getTetromino2() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M - 2; j++) {
			int sum = map[i][j] + map[i][j + 1] + map[i][j + 2];
			if (i < N - 1)
				ansSum = max(ansSum, sum + map[i + 1][j + 1]);
			if (0 < i){
				ansSum = max(ansSum, sum + map[i - 1][j + 1]);
			}
		}
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> map[i][j];
	for(int i = 0; i < N; i++){
		for (int j = 0; j < M; j++) {
			visited[i][j] = true;
			DFS(i, j, 1, map[i][j]);
			visited[i][j] = false;
		}
	}
	getTetromino1();
	getTetromino2();
	cout << ansSum;
}

---