[BOJ] 14500 : 테트로미노 (JAVA) with DFS

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

14500번: 테트로미노

---

 

문제 풀이

이 조각들을 좌표에 배치시켜, 해당 좌표에 쓰인 숫자들의 합의 최댓값을 구하는 문제이다.

 

발상은 어렵지 않았다. DFS로 발생하는 모든 4칸의 경우의 수를 세면 되는 문제였다. 그렇게 간단하게 생각하고 풀어갔다.

DFS 함수에 cnt 변수를 전달해주면서 cnt가 4가 되면 그 상황에서의 숫자들의 합을 하나의 경우의 수로 보았다. 그들 중 최댓값을 구하면 된다.

 

하지만 이렇게 하면 위의 조각들 중 분홍색 조각을 어떻게 해도 나올 수가 없다. 중간에 갈라지는 모양이기 때문이다. 이 점을 간과했다.

 

따라서 cnt가 2일 경우에, 즉 2칸을 점령했을 때 따로 처리를 해주었다. 이 방법도 신박했다. 주석을 참고하자.

 

import java.io.*;
import java.util.*;

public class Main {
    private static final int[] di = new int[] {-1, 0, 0, 1};
    private static final int[] dj = new int[] {0, -1, 1, 0};
    private static final int[][] board = new int[501][501];
    private static final boolean[][] used = new boolean[501][501];
    private static int mx, N, M;

    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());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                used[i][j] = true;
                dfs(i, j, board[i][j], 1);
                used[i][j] =false;
            }
        }
        System.out.println(mx);
    }

    private static void dfs (int i, int j, int sum, int cnt) {

        if (cnt == 4) {
            mx = Math.max(mx, sum);
            return;
        }
        for (int k = 0; k < 4; k++) {
            int ni = i + di[k];
            int nj = j + dj[k];
            if (ni < 0 || ni > N-1 || nj < 0 || nj > M-1 || used[ni][nj]) continue;
            //분홍색 조각을 카운트하기 위해
            //board[ni][nj] 를 갔다가 다시 board[i][j]로 온 것처럼
            //sum에는 board[ni][nj] 의 값을 전달하고 위치는 현재 위치로 전달한다.
            if (cnt == 2) {
                used[ni][nj] = true;
                dfs(i, j, sum + board[ni][nj], cnt+1);
                used[ni][nj] = false;
            }
            used[ni][nj] = true;
            dfs(ni, nj, sum + board[ni][nj], cnt+1);
            used[ni][nj] = false;
        }
    }
}