[JAVA] 백준 14500번- 테트로미노

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

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

public class Main{
    static int[][] arr;
    static int n, m;
    static boolean[][] visit;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int max = Integer.MIN_VALUE;

    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());

         arr = new int[n][m];
         visit = new boolean[n][m];

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

         for(int i=0; i<n; i++){
             for(int j=0; j<m; j++){
                 visit[i][j] = true;
                 dfs(i, j, 1, arr[i][j]);
                 visit[i][j] = false;
                 dfs2(i, j, 1, arr[i][j], 0);
             }
         }
        System.out.println(max);
    }

    static void dfs2(int x, int y, int cnt, int sum, int start){

        if(cnt == 4){
            max = Math.max(max, sum);
            return;
        }
        for(int i=start; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            dfs2(x, y, cnt+1, sum+arr[nx][ny], i+1);
        }
    }

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

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<0 || nx>=n || ny<0 || ny>=m || visit[nx][ny]) continue;

            visit[nx][ny] = true;
            dfs(nx, ny, cnt+1, sum+arr[nx][ny]);
            visit[nx][ny] = false;
        }
    }
}

 

 

보라색깔 도형의 경우 기존 dfs로는 찾을 수 없다.

맨 가운데 (x,y)를 기준으로 해 세 방향으로 뻗어나가도록 해야한다.

그렇게 하기 위해 (x, y)로부터 위, 아래, 오른쪽, 아래쪽의 방향 중 세방향을 겹치지 않게 탐색하게 한다.