[백준] 14500번 테트로미노

1) 생각

<테트로미노> 무슨말일까 했는데 아래와 같은 블록의 형태를 의미한다.

다른 블록의 형태의 경우에는 탐색을 통해 만들 수 있지만 'ㅜ' 형태의 모양은 만들기 어렵다.

딱, 저형태만 되는것은 아니고 저 도형이 회전한 모양이면 어느 모양이던 가능하다.

처음 Stack으로 DFS를 구현해보고 재귀를 통해서도 구현해 본결과 Stack으로 구현할 경우 '맞았습니다'는 뜨지만 반복작업이 많아지므로 메모리와 실행시간이 다음과 같이 차이가 나게된다.

그리고 이 문제처럼 입력이 띄엄띄엄 많이 주어진 경우 Scanner와 BufferedReader의 능력 차이를 쉽게 알아볼 수 있으므로 같은 코드에서 문자열 입력을 다르게 했을 때 생기는 차이는 다음과 같다.(Scanner는 1024chars의 버퍼 사이즈를 BufferedReader는 8192chars 사이즈를 처리할 수 있기 때문이다.)

따라서 입력의 개수가 많은 경우 BufferedReader를 쓰는것이 좋단걸 다시금 확인하였다.

2) 방안

'ㅜ','ㅏ','ㅓ','ㅗ'의 모양은 미리 모양을 배열로 지정해두고 탐색을 진행했고 그 외 나머지의 경우에는 DFS를 통해서 구현을 하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main{
    static int n,m;
    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());
        int[][] 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());
        }
        visited = new boolean[n][m];
        
        // 점을 기준으로 4개 충족 구하기(solve1)
        // 구하기 힘든 모양 직접 구하기(solve2)
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                solve(arr,i,j,1,arr[i][j]);
                solve2(arr,i,j);
            }
        }
        System.out.println(result);
    }
    static boolean[][] visited;
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    static int result = 0;
    private static void solve(int[][] arr,int x,int y,int idx,int sum) {
        if(idx==4) {
            result = Math.max(result, sum);
            return;
        }
        if(idx>4) return;
        visited[x][y] = true;
        for(int i=0;i<4;i++) {
            int tx = x+dir[i][0];
            int ty = y+dir[i][1];
            if(tx<0 || ty<0 || tx>=n || ty>=m) continue;
            if(visited[tx][ty]) continue;
            solve(arr,tx,ty,idx+1,sum+arr[tx][ty]);
        }
        visited[x][y] = false;
    }
    // ㅜ ㅏ ㅗ ㅓ
    static int[][][] shape = {{{0,0},{0,1},{0,2},{1,1}}
                             ,{{0,0},{1,0},{2,0},{1,1}}
                             ,{{0,0},{0,1},{0,2},{-1,1}}
                             ,{{0,0},{2,0},{1,0},{1,-1}}};
    
    private static void solve2(int[][] arr,int x,int y) {
        for(int i=0;i<4;i++) {
            int sum = 0;
            for(int j=0;j<4;j++) {
                int tx = x + shape[i][j][0];
                int ty = y + shape[i][j][1];
                if(tx<0 || ty<0 || tx>=n || ty>=m) break;
                sum += arr[tx][ty];
            }
            result = Math.max(result, sum);
        }
    }
}