[알고리즘] 백준 15686번 테트로미노 :: 우유

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

14500번: 테트로미노

 

코드 설명

테트리스의 모양처럼 생긴 블록들이 알고보면 DFS의 방향대로 탐색할때의 모양이라는 것을 알아낼 수 있었다.
DFS를 visited배열을 true 해주면서 depth가 4일때까지 돌리고 빠져나오면서 visited 배열을 false 해주는 백트래킹 방식으로 구현하였다.

여기서 핵심인 부분은 'ㅏ,ㅗ,ㅜ,ㅓ' 에 대한 블록을 어떻게 처리해줄까였는데
나는 cnt == 2 일때 arr[ny][nx] 의 값을 더해준 뒤 다른 ny,nx가 아닌 다른 방향으로 DFS를 한번 더 돌려서
sum 값을 계산하였다.

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

public class Main {

    static int N, M;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};
    static int ans = Integer.MIN_VALUE;

    public static void main(String[] agrs) 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];
        visited = 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++) {
                visited[i][j] = true;
                DFS(i, j, 0, 0);
                visited[i][j] = false;
            }
        }
        System.out.println(ans);
    }

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

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

            if (ny < 0 || nx < 0 || N <= ny || M <= nx)
                continue;

            if (visited[ny][nx])
                continue;

            if (cnt == 2) {
                visited[ny][nx] = true;
                DFS(y, x, sum + arr[ny][nx], cnt + 1);
                visited[ny][nx] = false;
            }

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

    }
}