https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
코드설명
구현(Implementation) + Simulation(시뮬레이션) + Brute Force(완전탐색) 문제입니다.
처음에는 각 테트로미노를 아래와 같이 각 테트로미노종류에 따라서 모든 풀리오미노를 표현하여 진행하려고했습니다만, 너무 많은 코드량이 존재하였습니다.
//[테트로미노종류][회전Index][내부테트로미노갯수 4개 고정][row냐, col이냐 2개 고정]
tetromino = new int[5][][][];
tetromino[0] = new int[2][4][2];
tetromino[0][0][0][0] = 0; tetromino[0][0][0][1] = 1; //(0, 1)
tetromino[0][0][1][0] = 0; tetromino[0][0][1][1] = 2; //(0, 2)
tetromino[0][0][2][0] = 0; tetromino[0][0][2][1] = 3; //(0, 3)
tetromino[0][0][3][0] = 0; tetromino[0][0][3][1] = 4; //(0, 4)
tetromino[0][1][0][0] = 0; tetromino[0][1][0][1] = 0; //(0, 0)
tetromino[0][1][1][0] = 1; tetromino[0][1][1][1] = 0; //(1, 0)
tetromino[0][1][2][0] = 2; tetromino[0][1][2][1] = 0; //(2, 0)
tetromino[0][1][3][0] = 3; tetromino[0][1][3][1] = 0; //(3, 0)
tetromino[1] = new int[1][4][2];
tetromino[1][0][0][0] = 0; tetromino[1][0][0][1] = 0; //(0, 1)
tetromino[1][0][1][0] = 0; tetromino[1][0][1][1] = 1; //(0, 2)
tetromino[1][0][2][0] = 1; tetromino[1][0][2][1] = 0; //(0, 3)
tetromino[1][0][3][0] = 1; tetromino[1][0][3][1] = 1; //(0, 4)따라서 위와 같이 각 직접 위치를 선정하지않고,
선언과 동시에 초기화 해보겠습니다.
//가변배열이기에 바로 할당하며 사이즈를 조절합니다.
//[폴리오미노 Type : 5][회전종류 : 가변][각 정사각형 위치 : 4][row와 col 좌표 : 2]
public static int[][][][] tetromino = new int[][][][]
{
{
{
{0, 0}, {0, 1}, {0, 2}, {0, 3}
},
{
{0, 0}, {1, 0}, {2, 0}, {3, 0}
}
},
{
{
{0, 0}, {0, 1}, {1, 0}, {1, 1}
}
},
{
{
{0,0}, {1, 0}, {2, 0}, {2, 1}
},
{
{0, 0}, {0, 1}, {0, 2}, {1, 0}
},
{
{0, 0}, {0, 1}, {1, 1}, {2, 1}
},
{
{0, 2}, {1, 0}, {1, 1}, {1, 2}
},
//대칭한후 4가지방향.
{
{0, 1}, {1, 1}, {2, 0}, {2, 1}
},
{
{0, 0}, {1, 0}, {1, 1}, {1, 2}
},
{
{0, 0}, {0, 1}, {1, 0}, {2, 0}
},
{
{0, 0}, {0, 1}, {0, 2}, {1, 2}
}
},
{
{
{0, 0}, {1, 0}, {1, 1}, {2, 1}
},
{
{0, 1}, {0, 2}, {1, 0}, {1, 1}
},
//대칭한후 회전
{
{0, 1}, {1, 0}, {1, 1}, {2, 0}
},
{
{0, 0}, {0, 1}, {1, 1}, {1, 2}
}
},
{
{
{0, 0}, {0, 1}, {0, 2}, {1, 1}
},
{
{0, 0}, {1, 0}, {2, 0}, {1, 1}
},
{
{0, 1}, {1, 0}, {1, 1}, {1, 2}
},
{
{0, 1}, {1, 0}, {1, 1}, {2, 1}
}
}
};
문제에서 처음에 놓쳣던 부분은 "대칭"을 시킬 수 있다는 점입니다.
각 폴리오미노를 대칭하면 바뀌는지 확인하는 방법은, 가운데 폴리오미노를 잘랐을때 양옆이 대칭이 아니라면 대칭 또한 포함시켜줍니다.
추가적인 팁으로는, 위의 코드에서 테트로미노 종류는 중요하지 않고, 단순히 수들의 합을 최대로 만족하는 테트로미노를 찾아서 위치시키는 것 입니다.
즉, 테트로미노종류를 나타내는 차원을 삭제시키고, 4차원에서 3차원으로 만들어 가변배열을 처리하는것도 가능합니다
static int [][][] tetromino = new int[][][]
{
//1번테트로
{ {0,0}, {0,1}, {0,2}, {0,3} },
{ {0,0}, {1,0}, {2,0}, {3,0} },
//2번테트로미노
{ {0,0}, {0,1}, {1,0}, {1,1} },
//3번테트로미노
{ {0,0}, {1,0}, {2,0}, {2,1} },
{ {0,0}, {0,1}, {0,2}, {1,0} },
{ {0,0}, {0,1}, {1,1}, {2,1} },
{ {0,2}, {1,0}, {1,1}, {1,2} },
//대칭한상태에서 시계방향
{ {0,1}, {1,1}, {2,0}, {2,1} },
{ {0,0}, {1,0}, {1,1}, {1,2} },
{ {0,0}, {0,1}, {1,0}, {2,0} },
{ {0,0}, {0,1}, {0,2}, {1,2} },
//4번테트로미노
{ {0,0}, {1,0}, {1,1}, {2,1} },
{ {0,1}, {0,2}, {1,0}, {1,1} },
{ {0,1}, {1,0}, {1,1}, {2,0} },
{ {0,0}, {0,1}, {1,1}, {1,2} },
//5번테트로미노
{ {0,0}, {0,1}, {0,2}, {1,1} },
{ {0,1}, {1,0}, {1,1}, {2,1} },
{ {0,1}, {1,0}, {1,1}, {1,2} },
{ {0,0}, {1,0}, {1,1}, {2,0} }
};
이제 각 폴리오미노를 모두 해당 map에 위치시키면서 진행합니다.
이떄, 범위를 벗어난다면 해당 폴리오미노는 위치시키지 못하므로 해당 폴리오미노는 계산에 포함시키지 않습니다.
코드
4차원으로 처리한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
public static int N,M, K;
public static int[][] map;
public static int answer =0;
//가변배열이기에 바로 할당하며 사이즈를 조절합니다.
//[폴리오미노 Type : 5][회전종류 : 가변][각 정사각형 위치 : 4][row와 col 좌표 : 2]
public static int[][][][] tetromino = new int[][][][]
{
{
{
{0, 0}, {0, 1}, {0, 2}, {0, 3}
},
{
{0, 0}, {1, 0}, {2, 0}, {3, 0}
}
},
{
{
{0, 0}, {0, 1}, {1, 0}, {1, 1}
}
},
{
{
{0,0}, {1, 0}, {2, 0}, {2, 1}
},
{
{0, 0}, {0, 1}, {0, 2}, {1, 0}
},
{
{0, 0}, {0, 1}, {1, 1}, {2, 1}
},
{
{0, 2}, {1, 0}, {1, 1}, {1, 2}
},
//대칭한후 4가지방향.
{
{0, 1}, {1, 1}, {2, 0}, {2, 1}
},
{
{0, 0}, {1, 0}, {1, 1}, {1, 2}
},
{
{0, 0}, {0, 1}, {1, 0}, {2, 0}
},
{
{0, 0}, {0, 1}, {0, 2}, {1, 2}
}
},
{
{
{0, 0}, {1, 0}, {1, 1}, {2, 1}
},
{
{0, 1}, {0, 2}, {1, 0}, {1, 1}
},
//대칭한후 회전
{
{0, 1}, {1, 0}, {1, 1}, {2, 0}
},
{
{0, 0}, {0, 1}, {1, 1}, {1, 2}
}
},
{
{
{0, 0}, {0, 1}, {0, 2}, {1, 1}
},
{
{0, 0}, {1, 0}, {2, 0}, {1, 1}
},
{
{0, 1}, {1, 0}, {1, 1}, {1, 2}
},
{
{0, 1}, {1, 0}, {1, 1}, {2, 1}
}
}
};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
//각 테트로미노가 Map을 모두 돌것입니다.
for(int type=0;type<5;type++) {
for(int rotate=0;rotate<tetromino[type].length;rotate++) {
for(int r=0;r<N;r++) {
for(int c=0;c<M;c++) {
int sum = 0;
boolean flag = false;
for(int i=0;i<4;i++) {
int nr = r + tetromino[type][rotate][i][0];
int nc = c + tetromino[type][rotate][i][1];
//범위를 벗어나면 count하지 않습니다.
if(nr < 0 || nr >= N || nc < 0 || nc >= M) {
flag = true;
break;
}
sum += map[nr][nc];
}
//해당 범위안에 있는경우만 작동합니다.
if(flag == false) {
answer = Math.max(answer, sum);
}
}
}
}
}
System.out.println(answer);
}
}
3차원으로 처리한 코드
public class Main {
static int N;
static int M;
static int[][] map;
// static int [][][] tetromino = new int[5][4][2];
// static boolean[][] visited;
static int maxresult = Integer.MIN_VALUE;
static int [][][] tetromino = new int[][][]
{
//1번테트로
{ {0,0}, {0,1}, {0,2}, {0,3} },
{ {0,0}, {1,0}, {2,0}, {3,0} },
//2번테트로미노
{ {0,0}, {0,1}, {1,0}, {1,1} },
//3번테트로미노
{ {0,0}, {1,0}, {2,0}, {2,1} },
{ {0,0}, {0,1}, {0,2}, {1,0} },
{ {0,0}, {0,1}, {1,1}, {2,1} },
{ {0,2}, {1,0}, {1,1}, {1,2} },
//대칭한상태에서 시계방향
{ {0,1}, {1,1}, {2,0}, {2,1} },
{ {0,0}, {1,0}, {1,1}, {1,2} },
{ {0,0}, {0,1}, {1,0}, {2,0} },
{ {0,0}, {0,1}, {0,2}, {1,2} },
//4번테트로미노
{ {0,0}, {1,0}, {1,1}, {2,1} },
{ {0,1}, {0,2}, {1,0}, {1,1} },
{ {0,1}, {1,0}, {1,1}, {2,0} },
{ {0,0}, {0,1}, {1,1}, {1,2} },
//5번테트로미노
{ {0,0}, {0,1}, {0,2}, {1,1} },
{ {0,1}, {1,0}, {1,1}, {2,1} },
{ {0,1}, {1,0}, {1,1}, {1,2} },
{ {0,0}, {1,0}, {1,1}, {2,0} }
};
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new int[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
map[i][j] = sc.nextInt();
}
}
simulate();
System.out.println(maxresult);
}
public static void simulate() {
for(int tetrominoindex = 0;tetrominoindex<tetromino.length;tetrominoindex++) {
// System.out.println("what?");
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
boolean breakflag = false;
// visited = new boolean[N][M];
int result = 0;
for(int k=0;k<tetromino[tetrominoindex].length;k++) {
int row = i + tetromino[tetrominoindex][k][0];
int col = j + tetromino[tetrominoindex][k][1];
if(row >=0 && row < N && col >= 0 && col < M) {
// visited[row][col] = true;
result += map[row][col];
}else {
breakflag = true;
break;
}
// if(row < 0 || row >= N || col < 0 || col >= M) {
// breakflag = true;
// break;
// }else if(row >=0 && row < N && col >= 0 && col < M) {
// visited[row][col] = true;
// }
}
if(breakflag == false) {
// int result = 0;
// for(int k=0;k<N;k++) {
// for(int h=0;h<M;h++) {
// if(visited[k][h] == true) {
// result+=map[k][h];
// }
// }
// }
maxresult = Math.max(maxresult, result);
}
}
}
}
}
}