백준 14500번 테트로미노 완전탐색(brute-force) 알고리즘 문제 :: 코드자몽

[백준] 14500번 테트로미노

14500번: 테트로미노

풀이

 

 

이런 블록 형태의 문제가 나오면 실제로 도형을 그려보면서 문제를 푸는 것이 가장 좋은 방법인 것 같다. 먼저 N*M 크기의 종이 위에 블록 하나만 놓는다고 했으니 각 블록이 놓일 수 있는 모양 전부를 그려보았다. 회전과 뒤집기를 사용하여 모두 만들 수 있는 도형의 모양은 19가지가 나온다. 저는 문제를 풀기 위해 3차원 배열형식으로 좌측 상단을 (0,0)으로 생각하고 각 블록의 모형을 넣어서 풀기로 결정했습니다.

 

블록이 놓인 칸의 합을 구하기 위해서는 모든 블록이 종이 위로 올라가야 한다. 그런데, 배치를 할 수 없는 부분들도 존재하기 때문에 이러한 문제를 해결해줘야 한다. 세로 N 가로 M이라고 했을 때 아래와 같이 3*4 모형의 종이에서 예를 들어보자.

 

위와 같이 18번모양의 블록을 종이위에 올려놓을 수 있다. 종이를 그리드로 봤을 때 좌표 (N, M)이 (0,0)에 위치해있다. 하지만 이 블록은 전체 12개의 칸 중에 놓을 수 있는 위치의 경우는 몇 가지가 안된다.

 

 

해당 모양으로는 12가지의 좌표 위치 중 (0,0), (1,0), (2,0)의 위치 딱 3가지 경우에만 블록을 종이 위로 올릴 수 있다. 위 그림처럼 모양에 따라 종이에 올릴 수 있는 경우를 식으로 표현해보자. (확인할 모양의 세로를 소문자n, 가로를 소문자 m)

종이 위 블록을 올려놓을 수 있는 경우의 수 = (N+1-n)(M+1-m)

브루트 포스 알고리즘은 모든 경우의 수를 시도해보는 것이다. 하지만, 경우의 수 크기에 따라 사용 여부를 결정할 수 있다. 지금까지 알아낸 블록과 종이의 원리를 두고 문제를 풀기 위해 최대 몇 가지 경우의 수를 확인해야 하는지 알아보자.

 

먼저 총블록의 개수는 19개이다. 다음 종이 위의 각 좌표의 위치 세로 N, 가로 M을 한 번씩 거쳐야 한다. 이후 해당 좌표에서 블록 위치(4)의 각 숫자를 합해야 한다. 확인해야 할 최대 경우의 수는

총 블록 모양 개수 19 * 최대 N 500 * 최대 M 500 * 블록 위치 4 = 19,000,000

간단하게 계산한 값은 1900만 정도가 나왔다. 저의 기준은 1천만 정도의 경우의 수 이하인 경우에만 브루트 포스를 사용합니다. 하지만, 계산한 경우의 수에서 모든 블록의 위치를 확인하는 것이 아니고 블록이 밖으로 나갔다고 판단되었을 때 break 문이나 continue문을 사용하면 최대 대략 1000만 정도의 경우의 수로 줄일 수 있다고 판단해서 모두 확인해보기로 했습니다. 결과는 아슬아슬했지만, 문제없이 통과했습니다.

 통과 후 채점 현황에서 다른 풀이들의 결과를 확인했습니다. 확실히 코드의 길이는 다른 풀이보다 짧았으나 속도 측면에서는 겨우 통과했듯이 많이 느렸습니다. 조금 더 신경 써서 코드 개선을 해보면 더 좋은 결과를 얻을 수 있을 것 같네요.

 

Java

import java.util.*;
 
public class Main {
    static int[][][] BLOCKS = {
        {{0,0}, {0,1}, {0,2}, {0,3}}
        ,{{0,0}, {1,0}, {2,0}, {3,0}}
        ,{{0,0}, {1,0}, {0,1}, {1,1}}
        ,{{0,0}, {0,1}, {0,2}, {1,2}}
        ,{{0,0}, {1,0}, {2,0}, {0,1}}
        ,{{0,0}, {1,0}, {1,1}, {1,2}}
        ,{{2,0}, {0,1}, {1,1}, {2,1}}
        ,{{1,0}, {1,1}, {1,2}, {0,2}}
        ,{{0,0}, {0,1}, {1,1}, {2,1}}
        ,{{0,0}, {1,0}, {0,1}, {0,2}}
        ,{{0,0}, {1,0}, {2,0}, {2,1}}
        ,{{0,0}, {1,0}, {2,0}, {1,1}}
        ,{{1,0}, {0,1}, {1,1}, {1,2}}
        ,{{0,1}, {1,0}, {1,1}, {2,1}}
        ,{{0,0}, {0,1}, {0,2}, {1,1}}
        ,{{0,0}, {0,1}, {1,1}, {1,2}}
        ,{{0,1}, {1,1}, {1,0}, {2,0}}
        ,{{1,0}, {1,1}, {0,1}, {0,2}}
        ,{{0,0}, {1,0}, {1,1}, {2,1}}
    };
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] arr = new int[n][m];
        int max = 0;
        for(int i=0; i<n; i++){
            for (int j=0;  j<m; j++){
                arr[i][j] = sc.nextInt();
            }
        }
 
        for(int i=0; i<BLOCKS.length; i++){
            int[][] block = BLOCKS[i];
            for(int j=0; j<n; j++){
                middleLoop : for(int k=0; k<m; k++){
                    int sum = 0;
                    for(int l=0; l<4; l++){
                        if(j+block[l][0]>=n || k+block[l][1]>=m){
                            continue middleLoop;
                        }else{
                            sum += arr[j+block[l][0]][k+block[l][1]];
                        }
                    }
                    if(sum > max) max = sum;
                }
            }
        }
        System.out.println(max);
    }
}