[BOJ 14500] 테트로미노

문제

• BOJ 14500
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

문제에 있는 5가지 모양을 잘 조합해서 최대값을 구하는 문제이다.
2차원 배열에서 한 좌표를 기준으로 DFS를 4칸 돌리면 보기에 있는 모양이 회전,반전되어 구할 수 있다.
그런데 ‘ㅗ’모양은 DFS로 구할 수 없으므로 회전한 ‘ㅗ’,’ㅏ’,’ㅜ’,’ㅓ’의 4가지 모양이 될 수 있는 방향정보를 2차원 배열에 담아주고, 따로 함수를 만들어서 구해주었다.
풀고 나면 코드가 복잡하지 않지만, DFS로 풀어야겠다는 해결책을 생각해내기까지 시간이 오래 걸린 문제이다.

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

//테트로미노
//N * M
public class Main {

    static int N, M; //세로, 가로
    static int[][] map;
    static boolean[][] visited;
    static int Ans; //최대값
    static int[] di = {-1, 1, 0, 0};//상하좌우
    static int[] dj = {0, 0, -1, 1};

    static int other_di[][] = {{0, 0, 0, 1}, {0, 1, 2, 1}, {0, 0, 0, -1}, {0, -1, 0, 1}}; //ㅗ모양
    static int other_dj[][] = {{0, 1, 2, 1}, {0, 0, 0, 1}, {0, 1, 2, 1}, {0, 1, 1, 1}};

    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());

        map = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }//End input

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = true; //방문표시 해주고
                dfs(i, j, 1, map[i][j]);
                visited[i][j]= false;
                other_shape(i, j); //ㅗ모양 검사
            }
        }//그래프 탐색하면서 최대값 구함

        System.out.println(Ans);

    }

    private static void other_shape(int x, int y) {
        for(int i=0; i<4; i++){ //ㅗ의 네가지 모양 만들거임
            boolean isShape = true; //만들어지는지
            int sum = 0;

            for(int j=0; j<4; j++){ //4번 연결
                int nx = x + other_di[i][j];
                int ny = y + other_dj[i][j];

                if(nx<0 || nx>=N || ny<0 || ny>=M){ //범위 체크
                    isShape = false;
                    break; //이 모양은 안만들어짐
                }else sum += map[nx][ny];
            }

            if(isShape) Ans = Math.max(Ans, sum); //ㅗ모양 완성
        }
    }

    private static void dfs(int i, int j, int cnt, int sum) {

        if(cnt >= 4){ //테트로미노 완성
            Ans = Math.max(Ans, sum);
            return;
        }

        for (int d = 0; d < 4; d++) {
            int ni = i + di[d];
            int nj = j + dj[d];

            //범위, 방문 체크
            if (ni >= 0 && ni < N && nj >= 0 && nj < M && !visited[ni][nj]) {
                visited[ni][nj] = true;
                dfs(ni, nj, cnt+1, sum + map[ni][nj]);
                visited[ni][nj] = false;
            }

        }//End 4방향 탐색
    }
}