알고리즘
[백준] 14500 테트로미노 - Java
BGK97
2025. 1. 13. 22:22
[Gold IV] 테트로미노 - 14500
성능 요약
메모리: 31824 KB, 시간: 484 ms
분류
브루트포스 알고리즘, 구현
제출 일자
2025년 1월 13일 21:43:41
문제 설명
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
입력
첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
예제 입력 1
5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1예제 출력 1
19예제 입력 2
4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5예제 출력 2
20예제 입력 3
4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1예제 출력 3
7풀이 방법
19가지의 테트로미노 방식을 검사하여, 가장 큰 값이 나오는 경우를 찾아 출력하는 문제였다.
- 단순 구현 문제라고 생각하여 처음에는 19가지의 방식을 모두 메서드 형태로 만들어 구현하려고 했다.
- 그런 식으로 문제를 풀었다가, 유지보수가 너무 불편하여 다른 형태로 바꾸기로 하였다...
초기 풀이
- 각 이미지의 왼쪽 상단 점을 초점으로, 좌표 이동을 실시했다.
- 이러다 보니 T자형은 돌출부분 때문에 좌표에 따라 계산이 어려웠다.
// J자 블럭
private static int check_J_block(int a, int b, int max) {
int maxSum = 0;
sum = 0;
// 방법 1 오른쪽 한번 위쪽 두번
if (a - 2 >= 0 && b + 1 < M) {
sum = field[a][b] + field[a - 1][b] + field[a - 2][b] + field[a - 2][b + 1];
maxSum = Math.max(maxSum, sum);
}
sum = 0;
// 방법 2 오른쪽으로 두번 아래로 한번
if (a + 1 < N && b + 2 < M) {
sum = field[a][b] + field[a][b + 1] + field[a][b + 2] + field[a + 1][b + 2];
maxSum = Math.max(maxSum, sum);
}
sum = 0;
// 방법 3 아래로 두번 왼쪽 한번
if (a + 2 < N && b - 1 >= 0) {
sum = field[a][b] + field[a + 1][b] + field[a + 2][b] + field[a + 2][b - 1];
maxSum = Math.max(maxSum, sum);
}
sum = 0;
// 방법 4 왼쪽 두번 위로 한번
if (a - 1 >= 0 && b - 2 >= 0) {
sum = field[a][b] + field[a][b - 1] + field[a][b - 2] + field[a - 1][b - 2];
maxSum = Math.max(maxSum, sum);
}
return maxSum > max ? maxSum : max;
}- 초기에는 이런식으로 일일이 좌표 유효성 검사와 이동을 동시에 수행했었는데, 테스트 케이스부터 오류가 나면서 코드를 수정하기가 힘들어 다른 방법을 찾으려고 했다.
- 코드가 250줄이 나오더라...
바뀐 풀이법
- 좌표를, 3차원 배열에 저장하여 dx dy 처럼 방향성을 지정해주고, 한번에 검사하려고 했다.
- 또한, 좌표 이동도 먼저 이동 시킨 뒤에 valid를 통과하면, 그제서야 이동 검사를 수행하도록 하였다.
- 이후, 배열에 있는 좌표이동정보를 forEach문을 통해 가져와 비교를 했고, 값을 리턴하여 max와 비교하였다.
// 범위 벗어나는지 확인하는 함수
public static boolean isValid(int x, int y, int[][] shape) {
for (int[] delta : shape) {
int nx = x + delta[0];
int ny = y + delta[1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
return false;
}
return true;
}
// 값을 계산하는 함수
public static int carculate(int x, int y, int[][] shape) {
int sum = 0;
for (int[] delta : shape) {
int nx = x + delta[0];
int ny = y + delta[1];
sum += field[nx][ny];
}
return sum;
}- 일일이 코드를 검사하는 것보다 확실히 코드의 수가 줄었고, 눈에 보기도 편해진 것을 확인할 수 있다.
풀이 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 테트로미노 {
static int N, M;
static int[][] field;
// 총 19가지의 방식
static int[][][] tetrominoes = {
// I 블록
{ { 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 } },
{ { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 } },
// 정사각형
{ { 0, 0 }, { 0, 1 }, { 1, 0 }, { 1, 1 } },
// L 블럭
{ { 0, 0 }, { 1, 0 }, { 2, 0 }, { 2, 1 } },
{ { 0, 0 }, { 0, -1 }, { 0, -2 }, { 1, -2 } },
{ { 0, 0 }, { -1, 0 }, { -2, 0 }, { -2, -1 } },
{ { 0, 0 }, { 0, 1 }, { 0, 2 }, { -1, 2 } },
// J 블럭
{ { 0, 0 }, { 1, 0 }, { 2, 0 }, { 2, -1 } },
{ { 0, 0 }, { 0, -1 }, { 0, -2 }, { -1, -2 } },
{ { 0, 0 }, { -1, 0 }, { -2, 0 }, { -2, 1 } },
{ { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 2 } },
// S 블럭
{ { 0, 0 }, { 0, 1 }, { -1, 1 }, { -1, 2 } },
{ { 0, 0 }, { 1, 0 }, { 1, 1 }, { 2, 1 } },
// Z 블럭
{ { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 2 } },
{ { 0, 0 }, { 1, 0 }, { 1, -1 }, { 2, -1 } },
// T 블럭
{ { 0, 0 }, { 0, -1 }, { -1, 0 }, { 1, 0 } },
{ { 0, 0 }, { 0, 1 }, { -1, 0 }, { 1, 0 } },
{ { 0, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } },
{ { 0, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } },
};
public static void main(String[] args) throws IOException {
// 풀이 방법
// 1. 테트로미노 경우의 수 19가지를 모두 대입해본다.
// 작대기 2, 정사각형 1, L자(J자) 8, ㄹ자 4, 볼록 블럭 4개
// 2. 이 때, 범위를 넘어서면 바로 out
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// N * M 행렬
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
field = new int[N][M];
int max = 0;
// 값 생성
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
field[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
for (int[][] shape : tetrominoes) {
// 범위를 벗어나지 않으면 검사 진행
if (isValid(i, j, shape)) {
max = Math.max(carculate(i, j, shape), max);
}
}
}
}
//결과 출력
System.out.println(max);
}
// 범위 벗어나는지 확인하는 함수
public static boolean isValid(int x, int y, int[][] shape) {
for (int[] delta : shape) {
int nx = x + delta[0];
int ny = y + delta[1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
return false;
}
return true;
}
// 값을 계산하는 함수
public static int carculate(int x, int y, int[][] shape) {
int sum = 0;
for (int[] delta : shape) {
int nx = x + delta[0];
int ny = y + delta[1];
sum += field[nx][ny];
}
return sum;
}
}결과
회고
- 문제를 좀 분석해서 효율적으로 풀 수 있는 방법을 찾는 연습을 해야할 것 같다...
- delta를 사용해서 이동하는 문제는 DFS, BFS에서도 많이 활용되기 때문에 잘 기억해둬야할 것 같았다.