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

테트로미노

---

모든 테트로미노를 그려서 회전/대칭 시키기에는 경우에 수가 너무 많았다.

배열의 최대 크기 250,000 * 4방향씩 탐색 4^3=64 < 1억 으로 시간복잡도 측면에서는 브루트포스로 접근하더라도 넉넉하다.

즉, DFS 탐색을 통해 depth=4 까지 탐색을 하면 대부분의 테트로미노에 대해 접근할 수 있다.

대부분이라 하면 예외가 존재하는데, ㅗ/ㅜ/ㅏ/ㅓ 가 그에 해당한다.
이 경우는 순차적인 DFS 탐색과 다르게 중심점에서 2개의 방향으로 동시에 뻗어나가서 계산해야 한다.

그렇기에 이 부분만 추가적으로 고려해서 depth=2 일때, 즉 중심점에 도착했을 때는 다음 정점을 방문처리 하고, 해당 중심점에서 다시 탐색을 돌려 결과값을 얻어내면 된다.

DFS 탐색을 할때마다 백트래킹을 적용해주어 모든 경우를 탐색할 수 있게 하면 된다.

---

코드

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

/*
2초, 512MB
---
테트로미노는 5가지 종류가 존재
N M 종위에 테트로미노 1개 놓기. 각각 칸에는 정수가 쓰여있음. 그 수 합을 최대로
테트로미노 회전 / 대칭 가능

(4 ≤ N, M ≤ 500) 최대 250,000 진행마다 4방향씩 탐색 4^3=64 이하
250,000 * 64 < 1억 으로 완전탐색 가능.

모든 테트로미노를 그려서 회전/대칭 시키기엔 너무 귀찮고 많다
그렇기에 DFS 를 통한 탐색으로 구현해보기

ㅗ/ㅜ/ㅓ/ㅏ 모양의 테트로미노는 백트래킹?
---
*/

public class Main {
    public static int n, m, result;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, -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];
        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());
            }
        }

        result = Integer.MIN_VALUE;
        visited = new boolean[n][m];
        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; // 모든 경우를 탐색하기 위한 백트래킹 처리
            }
        }

        System.out.println(result);
    }

    public static void dfs(int x, int y, int depth, int sum) {
        if (depth == 4) {
            result = Math.max(result, sum);
            return;
        }

        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny]) continue;

            if (depth == 2) { // 두번째 위치까지 방문 처리됐을 경우 == ㅗ/ㅜ/ㅏ/ㅓ 의 중간 부분까지 도착한 경우
                visited[nx][ny] = true;
                // 현재 위치에서 다음 부분 방문 처리 후, 나머지 부분 중 하나를 방문해서 모양을 맞춤
                dfs(x, y, depth + 1, sum + map[nx][ny]);
                visited[nx][ny] = false;
            }

            visited[nx][ny] = true;
            dfs(nx, ny, depth+1, sum+map[nx][ny]);
            visited[nx][ny] = false; // 모든 경우를 탐색하기 위한 백트래킹 처리
        }
    }
}