백준 14500 테트로미노(자바) - 삼성 sw 역량 인증

문제 풀이

1. 다른 모든 테트로미노는 dfs를 통해 depth가 4일 때의 모든 경우를 포함한다.

2. ㅓ ㅗ 모양의 경우 depth가 2일 때 다음 노드를 탐색했다고 생각하고, 실제 노드는 움직이지 않고 다음 dfs를 진행한다.

(dfs(x, y, depth+1, cnt+다음 노드의 값))

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

class Main {
    static int[][] map;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][] visited;
    static int n,m;
    static int answer = 0;
    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];
        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++) {
                visited[i][j] = true;
                dfs(i,j,1, map[i][j]);
                visited[i][j] = false;
            }
        }
        System.out.println(answer);
    }

    static void dfs(int x, int y, int depth, int cnt) {
        if (depth >= 4) {
            answer = Math.max(cnt, answer);
            return;
        }
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx<0 || ny<0 || nx>=n || ny>=m) continue;
            if (visited[nx][ny]) continue;
            if (depth == 2) {
                visited[nx][ny] = true;
                dfs(x,y,depth+1,cnt+map[nx][ny]);
                visited[nx][ny] = false;
            }
            visited[nx][ny] = true;
            dfs(nx, ny, depth+1, cnt+map[nx][ny]);
            visited[nx][ny] = false;
        }
    }
}