[백준 14500] 테트로미노

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

대충 어렇게 코드를짜겠다고 생각했으나 구현을 못해서 구글링을 하여 도움을 얻은 문제입니다.

https://jaimemin.tistory.com/623 글을 참조했습니다.

풀이

제가 생각하는 구현에 있어서 가장 중요한 부분은

1. 백트래킹기법을 쓸줄아느냐?(대충 이해하고 넘어가니 구현할 때 손도못댑니다.)

2. ㅗ,ㅜ,ㅏ,ㅓ의 도형 모양과 다른 테트로미노 도형의 모양의 차이가 무엇인지 아느냐?(dfs의 깊이가 다름을 관찰했나?)

3. 1,2번을 관찰하고 정확히 구현할줄 아는가?

이 3가지라고생각합니다. 

구현에 있어서 중요한 것은  ㅗ,ㅜ,ㅏ,ㅓ의 모양은 다른 모양들과 dfs깊이가 다르므로 따로 처리해주고, 나머지 모양은 모양과 상관없이 

시작점부터 일반적인dfs를 돌려주면 된다는 것입니다.(4번째 탐색했을 때 함수를 종료하면됩니다.) 모든 범위에서 탐색하므로 모든 모양들에 대해 탐색하기때문입니다.

그리고, ㅗ,ㅜ,ㅏ,ㅓ를 처리해줄 때 범위의 조건을 정확히 작성해야합니다. 이게 의외로 까다롭습니다. test case는 다 맞는데 게시판에있는 반례를 입력하니 범위가 이상해서 다른 답들이 나왔습니다.

사실 많이 허무하잖아요. 자신있게 풀었는데 반례때문에 그 문제가 통째로 틀리게되는거니깐....자기가 스스로 몇개의 경우를 만들어서 더 돌려보는 습관을 가져야겠습니다. 

마지막으로, 제일 중요한것은 백트래킹의 소스구현입니다. 이부분은 설명이 힘드니 소스코드로 확인해주세요.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int map[500][500], check[500][500], n, m;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int dfs(int y, int x, int cnt);
int func(int y, int x);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			check[i][j] = 1;
			//반환받아서 그 값으로 비교하기
			//1. 일반적인 dfs
			ans = max(ans, dfs(i, j, 1));
			//ㅗ,ㅓ,ㅏ,ㅜ의 특별한 형태
			ans = max(ans, func(i, j));
			//백트래킹
			check[i][j] = 0;
		}
	}
	cout << ans << '\n';

}
int dfs(int y, int x, int cnt)
{
	int sum = 0;
	if (cnt == 4)
	{
		return map[y][x];
	}
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= 0 && nx >= 0 && ny < n && nx < m && !check[ny][nx])
		{
			check[ny][nx] = 1;
			sum = max(sum, map[y][x] + dfs(ny, nx, cnt + 1));
			check[ny][nx] = 0;
		}
	}
	return sum;
}
int func(int y, int x)
{
	int sum = 0;
	//ㅏ
	if (y - 1 >= 0 && y + 1 < n && x + 1 < m)
		sum = max(sum, map[y][x] + map[y - 1][x] + map[y + 1][x] + map[y][x + 1]);
	//ㅓ
	if (y - 1 >= 0 && y + 1 < n && x + 1 < m)
		sum = max(sum, map[y][x] + map[y - 1][x + 1] + map[y + 1][x + 1] + map[y][x + 1]);
	//ㅗ
	if (y - 1 >= 0 && x - 1 >= 0 && x + 1 < m)
		sum = max(sum, map[y - 1][x] + map[y][x] + map[y][x - 1] + map[y][x + 1]);
	//ㅜ
	if (y + 1 < n && x - 1 >= 0 && x + 1 < m)
		sum = max(sum, map[y][x] + map[y][x - 1] + map[y][x + 1] + map[y + 1][x]);
	return sum;


}

결과