[코드트리 챌린지] 트로미노

코드트리 챌린지 첫주차 마지막 날이다. 

 

챌린지를 진행하기 위해 매주 진단 결과를 올려야 한다. 나의 진단 결과는 이렇다.

10일 만에 200점 가까이 올랐다

 

오늘 내가 푼 문제는 완전탐색 문제 중 하나인 트로미노 란 문제이다.

문제의 링크는 다음과 같다.
https://www.codetree.ai/missions/2/problems/tromino?&utm_source=clipboard&utm_medium=text

 

 

이 문제를 풀기 위해 떠올린 방법은 2중 for문으로 이차원 영역을 모두 순회하면서 블럭들을 대입해보며 비교하는 것이다. 그럴 경우 가능한 모든 형태의 블럭 6가지와 블럭을 구성하는 영역의 3개의 좌표를 알아내기 위해 N^2의 시간복잡도를 가진다고 생각했다. 그리고 블럭의 좌표와 현재 순회를 하고 있는 (i, j)좌표의 대입 결과 좌표가 이차원 배열의 범위를 벗어나면 해당 블럭을 건너뛰도록 하였다. 

 

위의 과정을 구현한 코드는 다음과 같다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NM = br.readLine().split(" ");
        int N = Integer.parseInt(NM[0]);
        int M = Integer.parseInt(NM[1]);
        int[][] table = new int[N][M];
        
        int[][][] BLOCK = {
            {{0,0}, {1, 0}, {1, 1}},
            {{0,0}, {0, 1}, {1, 1}},
            {{0,0}, {1, 0}, {0, 1}},
            {{1,0}, {1, 1}, {0, 1}},
            {{0,0}, {0, 1}, {0, 2}},
            {{0,0}, {1, 0}, {2, 0}}
        };    

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

        int maxSum = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                for(int[][] block : BLOCK){
                    int blockSum = 0;
                    for(int k = 0; k < 3; k++){
                        int dirX = i + block[k][0];
                        int dirY = j + block[k][1];
                        if(dirX >= 0 && dirX < N && dirY >= 0 && dirY < M){
                            blockSum += table[dirX][dirY];
                        }
                        else{
                            blockSum = 0;
                            break;
                        }                       
                    }
                    maxSum = (maxSum < blockSum) ? blockSum : maxSum;
                }
            }
        }//2차원 배열을 순회하며 각 블럭의 값 계산 및 비교

        System.out.println(maxSum);
    }       
}

 

다