[백준] 14500번 테트로미노

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

14500번: 테트로미노

 

import java.util.*;


public class Main {

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

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

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];
        visit = new boolean[N][M];

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
           		map[i][j] = sc.nextInt();
            }
        }

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                visit[i][j] = true;
                dfs(i, j, map[i][j], 1);
                visit[i][j] = false;
            }
        }
        System.out.println(max);  
    }

    private static void dfs(int y, int x, int sum, int count) {
        // 테트로미노 완성 시 수들의 합 중 최대값
        if(count >= 4 ) {
        	max = Math.max(max, sum);
        	return;
        }

        // 상하좌우 탐색
        for(int i = 0; i < 4; i++) {
            // 이동
            int ny = y + dy[i];
            int nx = x + dx[i];

            // 범위 벗어나는지 체크
            if(ny < 0 || ny >= N || nx < 0 || nx >= M ) {
            	continue;
            }

            // 아직 방문하지 않은 곳 처리
            if(!visit[ny][nx]) {

                // (ㅗ) 모양 탐색을 위해 2번째 칸에서 다시 상하좌우 탐색 ( ㅗ, ㅜ, ㅓ, ㅏ)
                if(count == 2) {
                    visit[ny][nx] = true;
                    dfs(y, x, sum + map[ny][nx], count + 1);
                    visit[ny][nx] = false;
                }

                // 이동한 것으로 탐색
                visit[ny][nx] = true;
                dfs(ny, nx, sum + map[ny][nx], count + 1);
                visit[ny][nx] = false;
            }
        }    
    }



}