[백준] 14500 테트로미노 JAVA

 

dfs를 활용한 구현문제

로직상으로는 bfs로 풀어도 상관없을 듯 하나, visit처리를 하기 힘들어 dfs로 구현하였다.

한칸씩 이동하며 모든 도형을 검사해야한다.

바로 인접한 칸으로 이동하면서 4칸을 이동하면 된다.

4칸째 이동하면 그간 지나친 경로의 숫자를 다 더한것과 max를 비교하여 max를 갱신한다.

 

ㅗ모양의 블럭은dfs로 해결이 안되어 해당 지점의 상하좌우에있는 블럭들을 모두 더한 뒤 하나씩 빼면서 최대치를 체크한다.

 

 

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

class Main {
    static int[][] map;
    static int N, M;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int max = 0;
    static boolean[][] visit;

    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());
            }
        }
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Point cur = new Point(i, j, 1, map[i][j]);
                dfs(cur);
                m(cur);
            }
        }
        System.out.println(max);
    }

    static void m(Point point) {
        int y = point.y;
        int x = point.x;
        int temp = point.sum;
        for (int i = 0; i < 4; i++) {
            int newY = y + dy[i];
            int newX = x + dx[i];
            if (newX >= M || newY >= N || newX < 0 || newY < 0) continue;
            temp += map[newY][newX];
        }
        for (int i = 0; i < 4; i++) {
            int newY = y + dy[i];
            int newX = x + dx[i];
            if (newX >= M || newY >= N || newX < 0 || newY < 0) {
                max = Math.max(max, temp);
                continue;
            }
            max = Math.max(max, temp - map[newY][newX]);
        }
    }

    static void dfs(Point point) {
        int y = point.y;
        int x = point.x;
        if (point.count == 4) {
            max = Math.max(max, point.sum);
            return;
        }
        visit[y][x] = true;
        for (int i = 0; i < 4; i++) {
            int newY = y + dy[i];
            int newX = x + dx[i];
            if (newX >= M || newY >= N || newX < 0 || newY < 0 || visit[newY][newX]) continue;
            dfs(new Point(newY, newX, point.count + 1, point.sum + map[newY][newX]));
        }
        visit[y][x] = false;
    }
}

class Point {
    int y, x, count, sum;

    Point(int y, int x, int count, int sum) {
        this.y = y;
        this.x = x;
        this.count = count;
        this.sum = sum;
    }
}