#14500: 테트로미노

백준 14500번: 테트로미노

문제:

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력:

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

풀이:

• 이 풀이는 개발아 담하자님의 블로그 포스팅을 참고하여 풀었다. 처음 이 문제를 풀때 테트로미노의 모든 모양의 경우의 수를 직접 구현할려고 하였다. 하지만, 이 방식은 너무 비효율적이여서 선택을 하지 않고 문제를 어떻게 풀지 다른 방법을 찾아보다가 개발아 담하자님의 블로그 포스팅을 보게 되었다.
• 개발아 담하자님의 블로그 포스팅의 방식은 ㅜ 모양을 제외한 모든 경우는 모두 방향 설정을 이용한 백트래킹 방식으로 합을 구할 수 있다는 것이다. ‘ㅜ’모양이 안되는 이유는 각 블록은 선택 된 후 4가지 방향을 갈 수 있다. 하지만, ‘ㅜ’모양은 대각선으로 이동해야 함으로 내가 처음에 모든 모양을 구현할려고 했던 것처럼 예외 처리를 해주어야 된다.
• 우선, 브루트 포스 문제이기 때문에 모든 경우의 수를 다 고려하여 시작점을 모든 자리에서 다 확인한다. 그리고, 그 자리에서 나올 수 있는 모든 모양의 경우의 수를 다 계산하여 최대 합을 저장한다. 앞서 말했듯이 ‘ㅜ’ 모양을 제외한 모든 모양의 경우의 수는 재귀함수를 이용하여 구현한다.
  • 재귀 함수에서는 범위 밖으로 나가거나 이미 방문한 상태이면 돌아가며 4가지 칸을 모두 만들었을 경우 합을 현재 최대 합과 비교하여 더 큰 값을 저장한다. 범위 밖이거나 방문하지 않았으면 방문 상태로 만든 뒤 방향을 더해주고 배열 값을 합해준 뒤 다음 칸으로 이동한다. 그리고 방문이 끝난 뒤에는 방문이 아닌 상태로 배열에 저장해 준다.
  • 예외 인 경우에는 4가지 모양 ㅓ, ㅏ, ㅜ, ㅗ를 모두 고려하여 현재 최대갑과 비교하여 큰 값을 저장해준다.

코드:

#include <iostream>

using namespace std;

//이동 방향을 위한 배열
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};

int n, m, answer = 0, arr[500][500];
bool visited[500][500];

//재귀함수를 이용하여 모든 경우의 수 확인
void brute_force(int y, int x, int sum, int cnt){
	//끝까지 도달한 경우
	if(cnt == 4){
		answer = max(answer, sum);
		return;
	}
	//범위 밖을 벗어난 경우
	if(x<0 || y<0 || x>=m || y>=n) return;
	//이미 방문한 상태인 경우
	if(visited[y][x]) return;
	//백트래킹 
	visited[y][x] = true; //현재 도착점을 방문한 곳으로 지정
	//모든 4가지 방향 고려하여 이동
	for(int i = 0; i < 4; i++) brute_force(y+dy[i],x+dx[i],sum+arr[y][x],cnt+1);
	//확인 끝난 자리는 다시 방문하지 않는 곳으로 바꿈
	visited[y][x] = false;	
}

int main(){
	//입력
	cin >> n >> m;
	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++){
			brute_force(i, j, 0, 0); //ㅜ모양을 제외한 모든 경우의 수의 합 출력
			//ㅗ,ㅜ 모양 예외 처리 
			if(j+2<m){
				int temp_sum = arr[i][j]+arr[i][j+1]+arr[i][j+2];
				//ㅗ모양이 가능한지 확인 
				if(i-1>=0) answer=max(answer,temp_sum+arr[i-1][j+1]);
				//ㅜ모양이 가능한지 확인 
				if(i+1<n) answer=max(answer,temp_sum+arr[i+1][j+1]);
			}
			//ㅓ,ㅏ모양 예외 처리 
			if(i+2<n){
				int temp_sum = arr[i][j]+arr[i+1][j]+arr[i+2][j];
				//ㅓ모양이 가능한지 확인 
				if(j-1>=0) answer=max(answer,temp_sum+arr[i+1][j-1]);
				//ㅏ모양이 가능한지 확인 
				if(j+1<m) answer=max(answer,temp_sum+arr[i+1][j+1]);
			}
		}
	}
	//출력 
	cout<<answer;
}