백준 14500 테트로미노

바보같은... dfs조차 사용하지 않고 단순하게 모든 경우 조사해도 금방 짤 수 있을 것 같은데? 라는 생각에서 쉽게 출발한 문제였다..

브루트포스 골드 4 문제이고, 자바를 이용하여 풀어보았다

자바 공부를 이제 막 시작하여, 코드가 자바의 어떤 정석적인 코드가 아닐 수 있다는 점을 참고해주기 바란다.

 

나의 접근은 이렇다.

테트로미노의 5가지 모양을, 

한 줄에 네 개가 연결된 모양, 정사각형 모양

한 줄에 세 개가 연결되고, 그 왼쪽 또는 오른쪽에 한 개의 블럭이 더 붙은 모양 // ㅓ ㅏ ㅗ ㅜ, L을 한 번에 처리

한 줄에 두 개가 연결되고, 그 왼쪽 또는 오른쪽 위아래로 두 개의 블럭이 붙어있는 모양

을 처리하는 세 가지 함수로 나누어 처리했다.

 

단점은, 각 경우에 대해 가로, 세로의 경우를 전부 따로 구현해줘야 한다는 점이다

 

그렇게 하여 탄생한 비효율적인 코드..

 

한 줄에 네 개가 연결된 모양, 정사각형 모양을 처리하는 함수

private static void check_four(){
        for(int i = 0; i < n; i++){
            for(int j = 3; j < m; j++){
                sum = array[i][j - 3] + array[i][j - 2] + array[i][j - 1] + array[i][j];
                if (sum > max)
                    max = sum;
            }
        }
        for(int i = 0; i < m; i++){
            for (int j = 3; j < n; j++){
                sum = array[j - 3][i] + array[j - 2][i] + array[j - 1][i] + array[j][i];
                if (sum > max)
                    max = sum;
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                sum = array[i - 1][j - 1] + array[i][j - 1] + array[i - 1][j] + array[i][j];
                if (sum > max)
                    max = sum;
            }
        }
    }

 

한 줄에 세 개가 연결되고, 그 왼쪽 또는 오른쪽에 한 개의 블럭이 더 붙은 모양을 처리하는 함수

private static void check_three(){
        for(int i = 0; i < n - 1; i++){
            for(int j = 2; j < m; j++){
                sum = array[i][j - 2] + array[i][j - 1] + array[i][j];
                for(int k = 2; k >= 0; k--){
                    sum = sum + array[i + 1][j - k];
                    if (sum > max)
                        max = sum;
                    sum = sum - array[i + 1][j - k];
                }
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 2; j < m; j++){
                sum = array[i][j - 2] + array[i][j - 1] + array[i][j];
                for(int k = 2; k >= 0; k--){
                    sum = sum + array[i - 1][j - k];
                    if (sum > max)
                        max = sum;
                    sum = sum - array[i - 1][j - k];
                }
            }
        }
                
        for(int i = 0; i < m - 1; i++){
            for(int j = 2; j < n; j++){
                sum = array[j - 2][i] + array[j - 1][i] + array[j][i];
                for(int k = 2; k >= 0; k--){
                    sum = sum + array[j - k][i + 1];
                    if (sum > max)
                        max = sum;
                    sum = sum - array[j - k][i + 1];
                }
            }
        }
        for(int i = 1; i < m; i++){
            for(int j = 2; j < n; j++){
                sum = array[j - 2][i] + array[j - 1][i] + array[j][i];
                for(int k = 2; k >= 0; k--){
                    sum = sum + array[j - k][i - 1];
                    if (sum > max)
                        max = sum;
                    sum = sum - array[j - k][i - 1];
                }
            }
        }
    }

 

한 줄에 두 개가 연결되고, 그 왼쪽 또는 오른쪽 위아래로 두 개의 블럭이 붙어있는 모양을 처리하는 함수

private static void check_two(){
        for(int i = 0; i < n - 1; i++){
            for(int j = 1; j < m - 1; j++){
                sum = array[i][j - 1] + array[i][j] + array[i + 1][j] + array[i + 1][j + 1];
                if (sum > max)
                    max = sum;
            }
        }
        for(int i = 1; i < m - 1; i++){
            for(int j = 0; j < n - 1; j++){
                sum = array[j][i] + array[j][i + 1] + array[j + 1][i - 1] + array[j + 1][i];
                if (sum > max)
                    max = sum;
            }
        }

        for(int i = 0; i < m - 1; i++){
            for(int j = 1; j < n - 1; j++){
                sum = array[j - 1][i] + array[j][i] + array[j][i + 1] + array[j + 1][i + 1];
                if (sum > max)
                    max = sum;
            }
        }
        for(int i = 1; i < n - 1; i++){
            for(int j = 0; j < m - 1; j++){
                sum = array[i][j] + array[i + 1][j] + array[i - 1][j + 1] + array[i][j + 1];
                if (sum > max)
                    max = sum;
            }
        }
    }

 

main

public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        max = 0;
        array = new int[n][m];

        for(int i = 0; i < n; i++){
            s = br.readLine();
            st = new StringTokenizer(s);
            
            for(int j = 0; j < m; j++){
                array[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        check_four();
        check_three();
        check_two();
        System.out.print(max);
        
    }

 

전체 코드

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

public class Main {
    private static int n, m, max, sum;
    private static int [][] array;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        max = 0;
        array = new int[n][m];

        for(int i = 0; i < n; i++){
            s = br.readLine();
            st = new StringTokenizer(s);
            
            for(int j = 0; j < m; j++){
                array[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        check_four();
        check_three();
        check_two();
        System.out.print(max);
        
    }

    private static void check_four(){
        for(int i = 0; i < n; i++){
            for(int j = 3; j < m; j++){
                sum = array[i][j - 3] + array[i][j - 2] + array[i][j - 1] + array[i][j];
                if (sum > max)
                    max = sum;
            }
        }
        for(int i = 0; i < m; i++){
            for (int j = 3; j < n; j++){
                sum = array[j - 3][i] + array[j - 2][i] + array[j - 1][i] + array[j][i];
                if (sum > max)
                    max = sum;
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                sum = array[i - 1][j - 1] + array[i][j - 1] + array[i - 1][j] + array[i][j];
                if (sum > max)
                    max = sum;
            }
        }
    }
    
    private static void check_three(){
        for(int i = 0; i < n - 1; i++){
            for(int j = 2; j < m; j++){
                sum = array[i][j - 2] + array[i][j - 1] + array[i][j];
                for(int k = 2; k >= 0; k--){
                    sum = sum + array[i + 1][j - k];
                    if (sum > max)
                        max = sum;
                    sum = sum - array[i + 1][j - k];
                }
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 2; j < m; j++){
                sum = array[i][j - 2] + array[i][j - 1] + array[i][j];
                for(int k = 2; k >= 0; k--){
                    sum = sum + array[i - 1][j - k];
                    if (sum > max)
                        max = sum;
                    sum = sum - array[i - 1][j - k];
                }
            }
        }
                
        for(int i = 0; i < m - 1; i++){
            for(int j = 2; j < n; j++){
                sum = array[j - 2][i] + array[j - 1][i] + array[j][i];
                for(int k = 2; k >= 0; k--){
                    sum = sum + array[j - k][i + 1];
                    if (sum > max)
                        max = sum;
                    sum = sum - array[j - k][i + 1];
                }
            }
        }
        for(int i = 1; i < m; i++){
            for(int j = 2; j < n; j++){
                sum = array[j - 2][i] + array[j - 1][i] + array[j][i];
                for(int k = 2; k >= 0; k--){
                    sum = sum + array[j - k][i - 1];
                    if (sum > max)
                        max = sum;
                    sum = sum - array[j - k][i - 1];
                }
            }
        }
    }

    private static void check_two(){
        for(int i = 0; i < n - 1; i++){
            for(int j = 1; j < m - 1; j++){
                sum = array[i][j - 1] + array[i][j] + array[i + 1][j] + array[i + 1][j + 1];
                if (sum > max)
                    max = sum;
            }
        }
        for(int i = 1; i < m - 1; i++){
            for(int j = 0; j < n - 1; j++){
                sum = array[j][i] + array[j][i + 1] + array[j + 1][i - 1] + array[j + 1][i];
                if (sum > max)
                    max = sum;
            }
        }

        for(int i = 0; i < m - 1; i++){
            for(int j = 1; j < n - 1; j++){
                sum = array[j - 1][i] + array[j][i] + array[j][i + 1] + array[j + 1][i + 1];
                if (sum > max)
                    max = sum;
            }
        }
        for(int i = 1; i < n - 1; i++){
            for(int j = 0; j < m - 1; j++){
                sum = array[i][j] + array[i + 1][j] + array[i - 1][j + 1] + array[i][j + 1];
                if (sum > max)
                    max = sum;
            }
        }
    }
}

 

굉장히 길고 불만족스러운 코드이다. DFS를 사용하는 방식과 6개의 블럭에서 최소값을 갖는 두 블럭을 제거하는 방식으로도 풀어보고자 한다. 추후 추가하도록 하겠다.