[백준 14500번] 테트로미노 :: 늦깎이 IT

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

이 문제는 단순히 DFS 탐색으로 풀 수 있습니다.

하지만, 아래 그림에 빨간 동그라미로 표시된 모양의 테트로미노는 DFS로 탐색할 수 없기 때문에 "ㅗ" 모양은

따로 처리해야합니다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int N, M, ans = Integer.MIN_VALUE;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[] dirX = new int[] { 0, 0, 1, -1 };
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][M];
        visited = new boolean[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());
            }
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dfs(i, j, 0, 1);
                check(i, j);
            }
        }
        System.out.println(ans);
    }
 
    public static void check(int row, int col) {
 
        int sum = map[row][col];
        int min = Integer.MAX_VALUE;
        int cnt = 0;
 
        for (int i = 0; i < 4; i++) {
            int nr = row + dirX[i];
            int nc = col + dirY[i];
            if (isBoundary(nr, nc)) {
                sum += map[nr][nc];
                cnt += 1;
                min = Math.min(min, map[nr][nc]);
            }
        }
        if (cnt == 4)
            sum -= min;
 
        ans = Math.max(ans, sum);
 
    }
 
    public static void dfs(int row, int col, int sum, int cnt) {
 
        if (cnt > 4) {
            ans = Math.max(ans, sum);
            return;
        }
 
        visited[row][col] = true;
        for (int i = 0; i < 4; i++) {
 
            int nr = row + dirX[i];
            int nc = col + dirY[i];
 
            if (isBoundary(nr, nc) && !visited[nr][nc])
                dfs(nr, nc, sum + map[nr][nc], cnt + 1);
        }
        visited[row][col] = false;
 
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < M);
    }
 
}
 
class Node {
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}