[Java] 백준 14500번 - 테트로미노

문제 링크 : https://www.acmicpc.net/problem/14500

 

List<int[][]> shapes = new ArrayList<>();
shapes.add(new int[][]{{1, 1, 1, 1}});
shapes.add(new int[][]{{1}, {1}, {1}, {1}});
shapes.add(new int[][]{{1,1}, {1, 1}});
shapes.add(new int[][]{{1,1}, {0,1}, {0,1}});
shapes.add(new int[][]{{1,1}, {1,0}, {1,0}});
shapes.add(new int[][]{{0,1}, {0,1}, {1,1}});
shapes.add(new int[][]{{1,0}, {1,0}, {1,1}});
shapes.add(new int[][]{{1,1,1}, {0,0,1}});
shapes.add(new int[][]{{0,0,1}, {1,1,1}});
shapes.add(new int[][]{{1,0,0}, {1,1,1}});
shapes.add(new int[][]{{1,1,1}, {1,0,0}});
shapes.add(new int[][]{{1,0}, {1,1}, {0,1}});
shapes.add(new int[][]{{0,1}, {1,1}, {1,0}});
shapes.add(new int[][]{{0,1,1}, {1,1,0}});
shapes.add(new int[][]{{1,1,0}, {0,1,1}});
shapes.add(new int[][]{{0,1,0}, {1,1,1}});
shapes.add(new int[][]{{1,1,1}, {0,1,0}});
shapes.add(new int[][]{{0,1}, {1,1}, {0,1}});
shapes.add(new int[][]{{1,0}, {1,1}, {1,0}});

가능한 모양의 행렬을 모두 추가해준다.

회전이나 대칭한 모양을 모두 고려하여 추가해주었다.

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

// input
int max = 0;

StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

int[][] matrix = new int[N][M];
for (int i = 0; i < N; i++) {
    matrix[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}

입력을 받는 부분

 

for (int[][] shape : shapes) {
    for (int rowStart = 0; rowStart <= N - shape.length; rowStart++) {
        for (int colStart = 0; colStart <= M - shape[0].length; colStart++) {
            int sum = 0;
            for (int i = 0; i < shape.length; i++) {
                for (int j = 0; j < shape[0].length; j++) {
                    if (shape[i][j] == 1)
                        sum += matrix[rowStart + i][colStart + j];
                }
            }
            max = Math.max(max, sum);
        }
    }
}

1번째 for 문 : 모든 가능한 모양들을 탐색한다.

2,3번째 for 문 : 각 모양이 전체 크기 N안에서 놓아질 수 있는 모든 위치의 시작점을 구한다.

4,5번째 for 문 : 각 모양의 전체 칸을 탐색하면서 종이 N에 놓아본다. 이때 겹치는 부분의 종이의 값을 더하면서 max값을 구한다.

 

 

bw.append(String.valueOf(max));
bw.flush();

br.close();
bw.close();

출력해주면 끝이다.