BOJ : 14500 테트로미노

---

[BOJ 14500(G5) 리뷰]

삼성 SW역량테스트 기출문제다.

처음엔 엄청 간단한 문제인 줄 알았다. 그냥 DFS로 구현하면 쉽게 풀릴것같아 쓱 구현해서 돌려보니 문제가 발생했다.

DFS로는 이 모양을 만족할 수가 없는것이였다.

어떻게 처리할까 매우 고민했다. 이왕 하는거 논리적이고 깔끔하게 코드를 짜고싶어서 머리를 이리저리 굴려보았는데 답이 잘 안나왔다. 계속 고민하다보니 집중력이 계속 떨어져서 그냥 무식한 방법을 사용하기로 했다.

DFS를하면서 두번째 블록에 위치할때, 위 모양이 나올 수 있는 경우의 수를 생각해서 그냥 인덱스로 접근해서 구해버렸다. 그나마 순열로 구현하는게 깔끔할테지만, 넥퍼뮤 사용법도 까먹고해서.. 그냥 무식하게 구해버렸다.

어쨌든 맞았으니 기분은 좋긴한데 왠지모를 찝찝함이 남아있는 문제다..

/*
	20.12.30
	BOJ : 14500 테트로미노 (https://www.acmicpc.net/problem/14500)
	브루트포스, 그래프탐색
*/

#include <bits/stdc++.h>
using namespace std;

int N, M;
int board[501][501];
bool vis[501][501];
int ans = 0;

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

void dfs(int r, int c, int cnt,int sum)
{
	cnt += 1;
	sum += board[r][c];
	if (cnt == 4) {
		ans = max(ans, sum);
		return;
	}

	if (cnt == 2) {
		vector <pair<int, int>> vc;
		for (int dir = 0; dir < 4; dir++) {
			int nx = r + dx[dir];
			int ny = c + dy[dir];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			if (vis[nx][ny]) continue;
			vc.push_back({ nx,ny });
		}

		if (vc.size() == 2) {
			ans = max(ans, sum + board[vc[0].first][vc[0].second] + board[vc[1].first][vc[1].second]);
		}
		else if (vc.size() == 3) {
			ans = max(ans, sum + board[vc[0].first][vc[0].second] + board[vc[1].first][vc[1].second]);
			ans = max(ans, sum + board[vc[1].first][vc[1].second] + board[vc[2].first][vc[2].second]);
			ans = max(ans, sum + board[vc[0].first][vc[0].second] + board[vc[2].first][vc[2].second]);
		}
	}

	for (int dir = 0; dir < 4; dir++) {
		int nx = r + dx[dir];
		int ny = c + dy[dir];
		if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
		if (vis[nx][ny]) continue;
	
		vis[nx][ny] = 1;
		dfs(nx, ny, cnt, sum);
		vis[nx][ny] = 0;
	}

}


int main() {
	cin >> N >> M;

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


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			vis[i][j] = 1;
			dfs(i, j, 0, 0);
			vis[i][j] = 0;
		}
	}

	cout << ans;
}