[코드트리/완전탐색] 트로미노

문제

https://www.codetree.ai/trails/complete/curated-cards/challenge-tromino/description

Code Tree | Learning to Code with Confidence

 

해결방법

2차원 영역에서 L모양과 I모양의 블럭을 자유롭게 회전하였을때 블록 안 숫자의 합이 가장 큰 값을 구해야한다. 문제의 제한을 보면 아래와 같다.

• 3 <= n, m <= 200
• 시간제한 : 1000ms
• 메모리 제한 : 80mib

주어진 제한에 따르면 O(n^2)의 시간복잡도여도 max 40,000이기때문에 이중반복문으로 전체 탐색을 해도 시간초과가 되지 않는다. 그러므로 완전탐색으로 이차원 영역을 탐색하며 현재위치(x,y) + 블럭영역1 + 블럭영역2의 값을 구하면 된다. L모양의 경우 현재위치를 중심으로 하여 상우, 우하, 하좌, 좌상 순서롤 영역을 갖고, I모양은 현재 위치를 중심으로 가로와 세로 총 3칸의 합을 구하면 된다. 

 

해당 방법으로 하면 O(n * m)으로 나타낼 수 있으며 max n * m * 6 = 240,000으로 시간초과가 발생하지 않는다.

소스코드

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static int M;
    public static void main(String[] args)  throws IOException{
        // Please write your code here.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        int[][] map = new int[N][M];

        for(int i = 0; i < N; i++){
            line = br.readLine().split(" ");
            for(int j = 0; j < M; j++){
                map[i][j] = Integer.parseInt(line[j]);
            }
        }

        int[] rot_x = {0, 1, 0, -1};
        int[] rot_y = {-1, 0, 1, 0};
        int max = 0;
        for(int y = 0; y < N; y++){
            for(int x = 0; x < M; x++){
                for(int k = 0; k < 4; k++){
                    if(positionCheck(x + rot_x[k], y + rot_y[k]) &&
                    positionCheck(x + rot_x[(k + 1) % 4], y + rot_y[(k + 1) % 4])){
                        int sum = map[y][x] + map[y + rot_y[k]][x + rot_x[k]] +
                        map[y + rot_y[(k + 1) % 4]][x + rot_x[(k + 1) % 4]];
                        max = Math.max(max, sum);
                    }
                }

                if(positionCheck(x, y - 1) && positionCheck(x, y + 1)){
                    int vSum = map[y][x] + map[y - 1][x] + map[y + 1][x];
                    max = Math.max(max, vSum);
                }
                
                
                if(positionCheck(x - 1, y) && positionCheck(x + 1, y)){
                    int hSum = map[y][x] + map[y][x - 1] + map[y][x + 1];
                    max = Math.max(max, hSum);
                }
            }
        }

        System.out.println(max);
    }

    public static boolean positionCheck(int x, int y){
        if(x < 0 || x >= M)
            return false;
        if(y < 0 || y >= N)
            return false;
        return true;
    }
}