[백준] 14500번: 테트로미노 - JAVA

🔗 문제 링크

BOJ 14500번: 테트로미노

14500번: 테트로미노

 

📝 풀이 과정

모든 테트로미노를 그린 뒤 탐색마다 도형을 회전시키고 대칭시키며 구할 수도 있지만 경우의 수가 너무 많아 귀찮아서 포기하였다...

 

예시로 그려진 테트로미노의 모양을 잘 살펴보면 ㅜ모양을 제외하면 DFS로 표현이 가능할 것이라는 생각이 들었다.

회색으로 칠해진 부분이 현재까지 탐색한 부분이고 ⭐의 위치가 현재 위치라고 할 때, 탐색할 수 있는 방향은 파란색의 화살표로 가는 방향뿐이기 때문에 ㅜ 모양의 탐색은 불가능하기 때문이다.

 

따라서, DFS를 depth가 4가 될 때까지 탐색을 한 결과를 구해준 뒤, ㅗ/ㅜ/ㅏ/ㅓ 의 형태를 가진 테트로미노를 따로 탐색해 주어야한다.

 

(y, x)을 기준으로 좌표를 잡아 모양이 map을 벗어나지 않는다면 범위 내의 합을 조회하며 max값을 갱신하였다.

 

⏱ 시간 복잡도

Map의 크기는 최대 250,000 (4 <= N,M <= 500),

한 점에서 DFS로 최대 탐색 가능한 경우는 진행마다 4방향씩 탐색하기 때문에 $4^3 = 64$ 이하(이미 방문한 점이 존재하는 방향은 건너 뛰기 때문에...)

 

따라서, 250,000 * 64 < 1억이므로 시간 내에 완전탐색이 가능하다.

 

💻 코드

import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static int[][] map;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][M];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                map[i][j] = sc.nextInt();

        boolean[][] visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visit[i][j] = true;
                dfs(i, j, 1, map[i][j], visit);
                visit[i][j] = false;
                check(i, j);
            }
        }
        System.out.println(ans);

    }

    static void dfs(int y, int x, int cnt, int sum, boolean[][] visit) {

        if (cnt >= 4) {
            ans = Math.max(ans, sum);
            return;
        }

        for (int k = 0; k < 4; k++) {
            int ny = y + dy[k];
            int nx = x + dx[k];

            if (ny < 0 || nx < 0 || ny >= N || nx >= M || visit[ny][nx]) {
                continue;
            }

            visit[ny][nx] = true;
            dfs(ny, nx, cnt + 1, sum + map[ny][nx], visit);
            visit[ny][nx] = false;
        }
    }

    static void check(int y, int x) {
        if (y < N - 2 && x < M - 1)
            ans = Math.max(ans, map[y][x] + map[y + 1][x] + map[y + 2][x] + map[y + 1][x + 1]);

        if (y < N - 2 && x > 0)
            ans = Math.max(ans, map[y][x] + map[y + 1][x] + map[y + 2][x] + map[y + 1][x - 1]);

        if (y < N - 1 && x < M - 2)
            ans = Math.max(ans, map[y][x] + map[y][x + 1] + map[y][x + 2] + map[y + 1][x + 1]);

        if (y > 0 && x < M - 2)
            ans = Math.max(ans, map[y][x] + map[y][x + 1] + map[y][x + 2] + map[y - 1][x + 1]);
    }


}

 

📊 제출 결과