백준 14500번 테트로미노 (JAVA)

백준 14500번 테트로미노 (JAVA)

문제

난이도

• 골드 4

알고리즘 분류

• 구현
• 브루트포스 알고리즘

풀이

테트로미노의 크기는 4

각 위치에서 4방 탐색으로 갈 수 있는 모든 위치를 4번 탐색하는 것은 모든 테트로미노의 경우의 수(대칭, 회전)을 탐색하는 것과 같다.

ㅗ, ㅏ, ㅜ, ㅓ 모양의 경우 한 방향으로 이어지지 않는다.

따라서 2번 때 탐색 시점에서 뻗어가는 경우를 계산한다.

코드

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

public class Main {

    static int N, M, answer;
    static int[][] arr;
    static boolean[][] visited;

    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };

    public static void main(String[] args) throws Exception {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(in.readLine());
            for (int m = 0; m < M; m++) {
                arr[n][m] = Integer.parseInt(st.nextToken());
            }
        }

        visited = new boolean[N][M];
        answer = 0;
        for (int n = 0; n < N; n++) {
            for (int m = 0; m < M; m++) {
                visited[n][m] = true;
                dfs(n, m, arr[n][m], 1);
                visited[n][m] = false;
            }
        }

        sb.append(answer);
        out.write(sb.toString());
        out.close();
    }

    private static void dfs(int row, int col, int sum, int cnt) {
        if (cnt == 4) {
            answer = Math.max(answer, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextRow = row + dx[i];
            int nextCol = col + dy[i];

            if (checking(nextRow, nextCol) && !visited[nextRow][nextCol]) {

                if (cnt == 2) {
                    visited[nextRow][nextCol] = true;
                    dfs(row, col, sum + arr[nextRow][nextCol], cnt + 1);
                    visited[nextRow][nextCol] = false;
                }

                visited[nextRow][nextCol] = true;
                dfs(nextRow, nextCol, sum + arr[nextRow][nextCol], cnt + 1);
                visited[nextRow][nextCol] = false;
            }
        }

    }

    private static boolean checking(int row, int col) {
        return ((0 <= row && row < N) && (0 <= col && col < M));
    }
}