알고리즘 재활 10일차 - 백준 테트로미노 14500번

어느덧 10일차.. 주말 어디갔어..

ㅋㅋ ㅋ근데 백수라 매일매일이 주말같아요..

 

테트로미노

 

 

 

문제를 잘 안읽었을때는 아..? 너무 어려운데 생각했었다

먼저 저 퍼즐 5개를 다쓰는줄.. 알았었다 호호

 

숫자가 적힌 보드가 주어지고, 해당 보드에 블록들 1개를 잘 배치해서 최대값을 구하는 문제였다.

대칭, 회전 전부 되므로 여간 까다롭게 느껴졌다. 블럭이 가능한 형태 모두를 하드코딩으로 넣어서.. 풀어주었다..

근데 고생해서 풀고 나니까 이거 그냥.. 이거 그냥 방향 맞춰서 4칸 탐색하면 됐구나

적다보니까 생각이 나버렸다

 

모야

 

 

진짜네.. 그냥 해당 방향으로 3칸 탐색하는 완전탐색이었구나 

물론 'ㅗ' 모양 블럭은 따로 로직을 만들어줘야겠다...

허탈하네

 

 

ㅋㅋ ㅋ ㅋ 중간에 사실 이상하게 나와서 하나하나 다 따져서 만들었던 바보가 저에요...

 

 

 

import java.io.*;
import java.util.*;
 
public class Main {// G4 테트로미노
    public static int N, M, max;
    public static int[][] arr;
 
    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());
        arr = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
//        algorithm(2, 2);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                algorithm(j, i);
            }
        }
        System.out.println(max);
    }
 
    public static void algorithm(int x, int y) {
        // 1자
        int[][][] block1 = {
                {{0, 1, 2, 3}, {0, 0, 0, 0}},
                {{0, 0, 0, 0}, {0, 1, 2, 3}}
        };
        // ㅁ 모양
        int[][][] block2 = {
                {{0, 1, 0, 1}, {0, 0, 1, 1}}
        };
        // L자
        int[][][] block3 = {
                {{0, 1, 2, 2}, {0, 0, 0, 1}}, // 아래 우측
                {{0, 1, 2, 2}, {0, 0, 0, -1}}, // 아래 좌측
                {{0, -1, -2, -2}, {0, 0, 0, 1}}, // 위 우측
                {{0, -1, -2, -2}, {0, 0, 0, -1}},  // 위 좌측
                {{0, 0, 0, -1}, {0, 1, 2, 2}}, //우측 위
                {{0, 0, 0, 1}, {0, 1, 2, 2}}, // 우측 아래
                {{0, 0, 0, -1}, {0, -1, -2, -2}}, // 왼쪽 위
                {{0, 0, 0, 1}, {0, -1, -2, -2}} // 왼쪽 아래
        };
        // 번개모양
        int[][][] block4 = {
                {{0, 1, 1, 2}, {0, 0, 1, 1}},   // 아래 우측
                {{0, 1, 1, 2}, {0, 0, -1, -1}}, // 아래 좌측
                {{0, -1, -1, -2}, {0, 0, 1, 1}}, // 위 우측
                {{0, -1, -1, -2}, {0, 0, -1, -1}}, // 위 좌측
                {{0, 0, -1, -1}, {0, 1, 1, 2}},   // 우측 아래
                {{0, 0, 1, 1}, {0, 1, 1, 2}}, // 우측 위
                {{0, 0, -1, -1}, {0, -1, -1, -2}}, // 좌측 위
                {{0, 0, 1, 1}, {0, -1, -1, -2}} // 좌측 아래
        };
 
        // 'ㅜ' 모양
        int[][][] block5 = {
                {{0, 0, 0, 1}, {0, 1, 2, 1}},  // 'ㅜ' 우측
                {{0, -1, -2, -1}, {0, 0, 0, 1}}, // 'ㅜ' 좌측
                {{0, 0, 0, 1}, {0, 1, 2, 1}},  // 'ㅗ' 우측
                {{0, 0, 0, -1}, {0, -1, -2, -1}},  // 'ㅗ' 왼쪽
                {{0, -1, -2, -1}, {0, 0, 0, -1}}, // 'ㅓ' 위쪽
                {{0, -1, -2, -1}, {0, 0, 0, 1}}, // 'ㅏ' 위쪽
                {{0, 1, 1, 2}, {0, 0, -1, 0}},  // 'ㅓ' 아래쪽
                {{0, 1, 2, 1}, {0, 0, 0, 1}}  // 'ㅏ' 아래쪽
        };
 
        int[][][][] blocks = {block1, block2, block3, block4, block5};
 
        for (int[][][] block : blocks) {
        for (int[][] shape : block) {
            int answer = 0;
            for (int k = 0; k < 4; k++) {
                int nx = x + shape[0][k];
                int ny = y + shape[1][k];
                if (range(nx, ny)) {
                    answer += arr[ny][nx];
                } else {
                    answer = 0;
                    break;
                }
            }
//            System.out.println("값 :" + answer + " x: " + x + ", y: " + y);
            max = Math.max(max, answer);
        }
//        System.out.println("블록 체인지");
        }
    }
 
    public static boolean range(int x, int y) {
        return x >= 0 && y >= 0 && x < M && y < N;
    }
}
 

 

주구장창 길지만..

방향 맞춰서 앞에 3칸 dfs로 완전탐색하고

ㅗ ㅜ ㅓ ㅏ 는 중앙에서 4가지 중 3가지 선택하는걸로 적용하면 쉬울것 같습니다..