bj14500(테트로미노) - DFS, 브루트포스

https://www.acmicpc.net/problem/14500

 

이 문제에서 깨달은 점은 DFS는 일직선으로 밖에 탐색을 못한다이다. 때문에, 예외가 적다면 예외를 처리하는 것을 두자.

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

public class Main {
    static int[] dy = {1,0,-1,0};
    static int[] dx = {0,1,0,-1};
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        System.out.println(brute_force());
    }

    private static int brute_force() {
        visited = new boolean[N][M];
        int max = 0;
        for(int y = 0; y < N; y++){
            for(int x = 0; x < M; x++){
                visited[y][x] = true;
                max = Math.max(getMax(y,x, map[y][x], 1), max);
                max = Math.max(checkExcept(y,x), max);
                visited[y][x] = false;
            }
        }
        return max;
    }

    private static int getMax(int y, int x, int value, int depth){
        int max = 0;
        if(depth == 4)return value;
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(!canGo(ny, nx))continue;
            visited[ny][nx] = true;
            max = Math.max(max, getMax(ny, nx, value + map[ny][nx], depth + 1));
            visited[ny][nx] = false;
        }
        return max;
    }

    private static int checkExcept(int y, int x) {
        int max = 0;
        if (y >= 1 && x >= 1 && x < M - 1)
            max = Math.max(max, map[y][x] + map[y-1][x] + map[y][x-1] + map[y][x+1]); // ㅗ
        if (y < N - 1 && x >= 1 && x < M - 1)
            max = Math.max(max, map[y][x] + map[y+1][x] + map[y][x-1] + map[y][x+1]); // ㅜ
        if (y >= 1 && y < N - 1 && x < M - 1)
            max = Math.max(max, map[y][x] + map[y-1][x] + map[y+1][x] + map[y][x+1]); // ㅏ
        if (y >= 1 && y < N - 1 && x >= 1)
            max = Math.max(max, map[y][x] + map[y-1][x] + map[y+1][x] + map[y][x-1]); // ㅓ
        return max;
    }

    private static boolean canGo(int y, int x) {
        return y >= 0 && y < N && x >= 0 && x < M && !visited[y][x];
    }

    private static void initialize() throws IOException {
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        map = new int[N][M];
        for (int y = 0; y < N; y++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int x = 0; x < M; x++) {
                map[y][x] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }
    }
}