[백준] 17085번 십자가 2개 놓기 (Java)

백준 17085 십자가 2개 놓기

DFS를 활용해 가능한 경우의 조합을 구하고 완전 탐색을 활용해 해결하는 문제다. 시행 착오를 많이 겪어서 겨우 해결한 문제다. 그 중 제일 시간을 많이 뺏었던 것은 점을 기준으로 가능한 가장 큰 십자가를 만드려고 했던 것이다. 1 X 9보단 5 X 5의 값이 더 크다는 것을 고려해서 십자가가 만들어질 수 있는 모든 경우에 대해서 대비를 했어야 했다.

1. 입력을 boolean 배열로 받아 '#'인 경우는 true로 저장한다.
2. "#"로 조합할 수 있는 모든 경우는 DFS를 활용하여 comb에 저장한다.
3. 십자가가 만들어질 수 있는 모든 경우를 완전 탐색하기 위해서 십자가의 크기는 중복 조합으로 정한다.
4. boolean deepcopy한 이후, 좌표의 위치는 false로 초기화를 먼저 해야 한다.
5. 이후에 좌표와 십자가의 크기를 활용해 십자가가 만들어지는지 확인한다.

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


public class Main {
    static int [] dx = new int[] {0, 1, 0, -1};
    static int [] dy = new int[] {1, 0, -1, 0};
    static int n, m, maxV = 0;
    static boolean[][] toVisit;
    static int[][] comb = new int[2][2];

    // 좌표와 십자가 크기를 바탕으로 가능한지 확인
    public static boolean check(int l1, int l2){
        int tmpY, tmpX;
        int y1 = comb[0][0];
        int x1 = comb[0][1];
        int y2 = comb[1][0];
        int x2 = comb[1][1];
        boolean res = true;
        boolean [][] tmpVisit = new boolean[n][m];

        // 배열 깊은 복사 (2차원 배열)
        for(int i = 0; i < n; i ++){
            tmpVisit[i] = toVisit[i].clone();
        }
        tmpVisit[y1][x1] = false;
        tmpVisit[y2][x2] = false;
        for (int i = 0; res && i < 4; i ++){
            for(int j = 1; res && j <= l1; j++){
                tmpY = y1 + j * dy[i];
                tmpX = x1 + j * dx[i];
                if(tmpY >= 0 && tmpY < n && tmpX >=0 && tmpX < m){
                    res &= tmpVisit[tmpY][tmpX];
                    tmpVisit[tmpY][tmpX] = false;
                } else{
                    res = false;
                }
            }
        }

        for (int i = 0; res && i < 4; i ++){
            for(int j = 1; res && j <= l2; j++){
                tmpY = y2 + j * dy[i];
                tmpX = x2 + j * dx[i];
                if(tmpY >= 0 && tmpY < n && tmpX >=0 && tmpX < m){
                    res &= tmpVisit[tmpY][tmpX];
                    tmpVisit[tmpY][tmpX] = false;
                } else{
                    res = false;
                }
            }
        }
        return res;
    }

    // 십자가 크기 중복 조합
    public static void simulate(){
        int l1, l2;
        for(int i = 0; i < 8; i ++){
            for(int j = 0; j < 8; j ++){
                l1 = i;
                l2 = j;
                // 가능하다면 최댓값 업데이트
                if(check(l1, l2)){
                    maxV = Math.max(maxV, (1 + 4 * l1) * (1 + 4 * l2));
                }
            }
        }
    }

    // 좌표 조합
    public static void dfs(int y, int x, int cnt){
        if(cnt == 2){
            simulate();
        } else if(y < n) {
            dfs(y + (x + 1) / m, (x + 1) % m, cnt);
            if (toVisit[y][x]){
                comb[cnt] = new int [] {y, x};
                dfs(y + (x + 1) / m, (x + 1) % m, cnt + 1);
            }
        }
    }


    public static void main(String[] args) {
        try {
            String tmp;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            toVisit = new boolean[n][m];
            for(int i = 0; i < n; i ++){
                tmp = br.readLine();
                for(int j = 0; j < m; j ++){
                    if(tmp.charAt(j) == '#'){
                        toVisit[i][j] = true;
                    }
                }
            }
            dfs(0, 0, 0);
            System.out.println(maxV);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}