백준 테트로미노 14500 java

문제링크

문제 접근

• 주어진 5개의 도형들을 회전해서 나올 수 있는 모든 경우의 수를 탐색한다.
• 시간 계산 -> 500 x 500 x 19(도형 갯수) x 4(사각형 4개 탐색)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class baek_14500 {
    static int N,M;
    static int[][] map;
    static int[] shape1_2_di = {1,2,3,0,0,0,1,0,1};
    static int[] shape1_2_dj = {0,0,0,1,2,3,0,1,1};
    static int[] shape3_di = {0,0,1,0,0,-1,0,1,2,0,-1,-2,1,2,0,1,2,2,1,0,0,1,1,1};
    static int[] shape3_dj = {1,2,2,1,2,2,1,1,1,1,1,1,0,0,1,0,0,1,0,1,2,0,1,2};

    static int[] shape4_di = {0,1,1,0,-1,-1,1,1,2,1,1,2};
    static int[] shape4_dj = {1,1,2,1,1,2,0,-1,-1,0,1,1};

    static int[] shape5_di = {1,1,2,1,1,2,1,1,1,0,0,1};
    static int[] shape5_dj = {0,-1,0,0,1,0,-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];

        int answer = 0;
        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());
            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                int idx = 0;
                for(int k=0;k<3;k++){
                    int sum = 0;
                    int nexti1 = i + shape1_2_di[idx];
                    int nextj1 = j + shape1_2_dj[idx++];
                    int nexti2 = i + shape1_2_di[idx];
                    int nextj2 = j + shape1_2_dj[idx++];
                    int nexti3 = i + shape1_2_di[idx];
                    int nextj3 = j + shape1_2_dj[idx++];
                    if(nexti1 >= 0 && nexti1 < N && nextj1 >= 0 && nextj1 < M && nexti2 >= 0 && nexti2 < N && nextj2 >= 0 && nextj2 < M && nexti3 >= 0 && nexti3 < N && nextj3 >= 0 && nextj3 < M){
                        sum += map[i][j] + map[nexti1][nextj1] + map[nexti2][nextj2] + map[nexti3][nextj3];
                    }
                    else{
                        continue;
                    }
                    answer = Math.max(answer,sum);
                }
                idx = 0;
                for(int k=0;k<8;k++){
                    int sum = 0;
                    int nexti1 = i + shape3_di[idx];
                    int nextj1 = j + shape3_dj[idx++];
                    int nexti2 = i + shape3_di[idx];
                    int nextj2 = j + shape3_dj[idx++];
                    int nexti3 = i + shape3_di[idx];
                    int nextj3 = j + shape3_dj[idx++];
                    if(nexti1 >= 0 && nexti1 < N && nextj1 >= 0 && nextj1 < M && nexti2 >= 0 && nexti2 < N && nextj2 >= 0 && nextj2 < M && nexti3 >= 0 && nexti3 < N && nextj3 >= 0 && nextj3 < M){
                        sum += map[i][j] + map[nexti1][nextj1] + map[nexti2][nextj2] + map[nexti3][nextj3];
                    }
                    else{
                        continue;
                    }
                    answer = Math.max(answer,sum);
                }
                idx = 0;
                for(int k=0;k<4;k++){
                    int sum = 0;
                    int nexti1 = i + shape4_di[idx];
                    int nextj1 = j + shape4_dj[idx++];
                    int nexti2 = i + shape4_di[idx];
                    int nextj2 = j + shape4_dj[idx++];
                    int nexti3 = i + shape4_di[idx];
                    int nextj3 = j + shape4_dj[idx++];
                    if(nexti1 >= 0 && nexti1 < N && nextj1 >= 0 && nextj1 < M && nexti2 >= 0 && nexti2 < N && nextj2 >= 0 && nextj2 < M && nexti3 >= 0 && nexti3 < N && nextj3 >= 0 && nextj3 < M){
                        sum += map[i][j] + map[nexti1][nextj1] + map[nexti2][nextj2] + map[nexti3][nextj3];
                    }
                    else{
                        continue;
                    }
                    answer = Math.max(answer,sum);
                }
                idx = 0;
                for(int k=0;k<4;k++){
                    int sum = 0;
                    int nexti1 = i + shape5_di[idx];
                    int nextj1 = j + shape5_dj[idx++];
                    int nexti2 = i + shape5_di[idx];
                    int nextj2 = j + shape5_dj[idx++];
                    int nexti3 = i + shape5_di[idx];
                    int nextj3 = j + shape5_dj[idx++];
                    if(nexti1 >= 0 && nexti1 < N && nextj1 >= 0 && nextj1 < M && nexti2 >= 0 && nexti2 < N && nextj2 >= 0 && nextj2 < M && nexti3 >= 0 && nexti3 < N && nextj3 >= 0 && nextj3 < M){
                        sum += map[i][j] + map[nexti1][nextj1] + map[nexti2][nextj2] + map[nexti3][nextj3];
                    }
                    else continue;
                    answer = Math.max(answer,sum);
                }
            }
        }
        System.out.print(answer);
    }
}

결과

정리

• 4번 도형 (--__ 모양) di, dj에서 실수해서 디버깅
• 도형을 나누어서 반복문 돌려서 코드가 길어짐
• 하지만 하나로 합치면 디버깅하기 어려웠을 듯