[백준] 14500 테트로미노 문제 풀어보기
1. 문제
1) 링크
2) 문제
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
.png)
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
3) 입력
첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
4) 출력
첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
더 자세한 문제의 제한을 보기 위해서는 위의 백준 링크를 클릭해보자.
2. 풀이
이 문제는 처음에 테트로미노를 다섯가지 종류에 대해서 90도씩 돌리는 모든 경우를 생각해볼 수 있다. 하지만 그렇게 접근을 하게 되면 경우의 수가 너무 많게 되는 문제가 생긴다. 코드를 쓰다가 오류를 범할 확률이 높아진다.
따라서 조금 더 쉽게 접근하기 위해서 이 문제는 테트로미노를 두 가지 종류로 나누어서 생각할 수 있다. 위의 그림에서 보라색 벽돌을 제외한 모든 테트로미노는 하나의 칸에서 시작하여 4칸을 총 이동하면 만들어지는 테트로미노이다. 그렇기 때문에 파란색, 노란색, 주황색, 연두색 테트로미노는 모두 재귀함수를 활용하여 문제를 해결 할 수 있다.
public static void algo(int x, int y, int sum, int count){
if(count==4){
if (ans<sum){
ans=sum;
}
return;
}
for(int i=0; i<4; i++){
int nx=x+dx[i];
int ny=y+dy[i];
if (nx>=0 && ny>=0 &&nx<n && ny<m && !check[nx][ny]){
check[x][y]=true;
algo(nx, ny, sum+a[x][y], count+1);
}
check[x][y]=false;
}
}재귀함수 부분의 코드만 살펴보겠다. 우선 총 count가 4번이 되면 테트로미노 하나를 완성했다는 뜻이므로 이때 값이 max인지를 확인하여 답을 업데이트해주는 과정을 거친다.
그리고 해당 칸이 방문되었는지를 확인하기 위해서 check 배열을 만들어주고 다음 칸이 범위 안에 있고 방문하지 않았을 경우에 다음 칸을 방문해준다. 이 경우에 sum을 업데이트해주고 count의 값은 하나를 증가시켜주면서 재귀함수를 호출하는 것이다.
위의 재귀함수를 쓰면 파란색, 노란색, 주황색, 초록색 테트로미노의 경우는 모두 해결할 수 있다. 하지만 보라색 테트로미노의 경우 하나의 칸에서 시작하여서 4개의 칸을 모두 재귀함수로는 방문할 수 없다는 문제점이 생긴다.
따라서 이 경우에만 특수하게 직접 모든 경우를 고려해주어 코드를 추가적으로 작성해준다.
if (i+2 < n) { //세로로 세워져있을 경우
int temp = a[i][j] + a[i+1][j] + a[i+2][j];
if (j+1 < m) { //오른쪽으로 돌출
int temp2 = temp + a[i+1][j+1];
if (ans < temp2) ans = temp2;
}
if (j-1 >= 0) { //왼쪽으로 돌출
int temp2 = temp + a[i+1][j-1];
if (ans < temp2) ans = temp2;
}
}
if (j+2 < m) { //가로로 눕혀있을 경우
int temp = a[i][j] + a[i][j+1] + a[i][j+2];
if (i-1 >= 0) { //아래로 향함
int temp2 = temp + a[i-1][j+1];
if (ans < temp2) ans = temp2;
}
if (i+1 < n) { //위로 향함
int temp2 = temp + a[i+1][j+1];
if (ans < temp2) ans = temp2;
}
}이런식으로 작성해 줄 수 있다. 위의 재귀함수도 호출하고, 위의 코드도 실행해주면 모든 경우에 대해서 최댓값을 구할 수 있다.
3. 코드
이를 모두 종합한 전체코드는 아래와 같다.
import java.util.*;
public class Main{
public static int a[][];
static boolean check[][];
static int ans=0;
static int n;
static int m;
static int []dx={1,-1,0,0};
static int []dy={0,0,1,-1};
public static void algo(int x, int y, int sum, int count){
if(count==4){
if (ans<sum){
ans=sum;
}
return;
}
for(int i=0; i<4; i++){
int nx=x+dx[i];
int ny=y+dy[i];
if (nx>=0 && ny>=0 &&nx<n && ny<m && !check[nx][ny]){
check[x][y]=true;
algo(nx, ny, sum+a[x][y], count+1);
}
check[x][y]=false;
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
a=new int[n][m];
check=new boolean[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
a[i][j]=sc.nextInt();
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
algo(i,j,0,0);
if (i+2 < n) {
int temp = a[i][j] + a[i+1][j] + a[i+2][j];
if (j+1 < m) {
int temp2 = temp + a[i+1][j+1];
if (ans < temp2) ans = temp2;
}
if (j-1 >= 0) {
int temp2 = temp + a[i+1][j-1];
if (ans < temp2) ans = temp2;
}
}
if (j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2];
if (i-1 >= 0) {
int temp2 = temp + a[i-1][j+1];
if (ans < temp2) ans = temp2;
}
if (i+1 < n) {
int temp2 = temp + a[i+1][j+1];
if (ans < temp2) ans = temp2;
}
}
}
}
System.out.println(ans);
}
}