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

문제 링크

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

문제

십자가는 가운데에 ''가 있고, 상하좌우 방향으로 모두 같은 길이의 ''가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 0보다 크거나 같아야 한다.

아래 그림은 크기가 0, 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.

십자가의 넓이는 포함된 '*'의 개수이다. 크기가 0, 1, 2, 3인 십자가의 넓이는 1, 5, 9, 13이다.

크기가 N×M이고, '.'과 '#'로 이루어진 격자판이 주어진다. 격자판에 두 개의 십자가를 겹치지 않게 놓으려고 한다. 십자가는 '#'가 있는 칸에만 놓을 수 있다. 놓인 십자가 넓이의 곱의 최댓값을 구해보자.

입력

첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 놓은 십자가 넓이의 곱의 최댓값을 출력한다.

알고리즘: 브루트 포스, 구현

풀이

N,M은 15가 최대이기 때문에 최대 사이즈는 7이다.

0~7사이즈 중에서 2개를 조합하는 모든 경우의 수를 구한다. 여기서 첫 번째 뽑은 수를 두 번째에서도 중복으로 뽑을 수 있다.

그리고 조합한 2개의 사이즈를 board에 들어갈 수 있는지 check를 한다. 2개의 사이즈가 겹치지 않고 들어가면 놓인 십자가 넓이의 곱과 ans값을 비교해서 최댓값을 갱신해주면 된다.

개인적으로 솔루션은 쉬운데 board에 십자가가 들어갈 수 있는지 체크하는 함수를 구현하는 게 조금 까다로웠다.

소스 코드

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

class Coordinate {
    int x, y;
    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int N,M;
    static char board[][];
    static Stack<Integer> result = new Stack<>();
    static int max_size;
    static int ans = -1;
    static final int dx[] = {-1, 0, 1, 0};
    static final int dy[] = {0, -1, 0 ,1};
    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());
        board = new char[N][M];
        max_size = (Math.min(N,M) * 2 - 1)/4;
        for(int i=0; i<N; i++) {
            String n_st = new String(br.readLine());
            for(int j=0; j<M; j++) {
                board[i][j] = n_st.charAt(j);
            }
        }
        DFS(0);
        System.out.println(ans);
    }
    static void DFS(int ind) {
        if(result.size()==2) {
            char copy_board[][] = new char[N][M];
            for(int i=0; i<copy_board.length; i++) {
                copy_board[i] = board[i].clone();
            }
            if(check(copy_board,result,0)) {
                int v = (result.get(0) * 4 + 1) * (result.get(1) * 4 + 1);
                ans = Math.max(ans, v);
            }
            return;
        }
        for(int i= ind; i<=max_size; i++) {
            result.push(i);
            DFS(i);
            result.pop();
        }
    }
    
    static boolean check(char cb[][] ,Stack<Integer> s, int si) {
        if(si == 2) return true;
        int size = s.get(si);
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(cb[i][j] == '#') {
                    boolean posi = true;
                    ArrayList<Coordinate> back = new ArrayList<>();
                    for(int k=0; k<4; k++) {
                        Coordinate nc = new Coordinate(j, i);
                        for(int a=0; a<size; a++) {
                            nc.x += dx[k];
                            nc.y += dy[k];
                            if((nc.x>=0 && nc.x<=M-1) && (nc.y>=0 && nc.y<=N-1)) {
                                if(cb[nc.y][nc.x] != '#') {
                                    posi = false;
                                    break;
                                } else {
                                    cb[nc.y][nc.x] = '*';
                                    back.add(new Coordinate(nc.x, nc.y));
                                }
                            } else {
                                posi = false;
                                break;
                            }
                            if(!posi) break;
                        }
                        if(!posi) break;
                    }
                    if(posi) {
                        if(check(cb, s, si+1)) return true;
                    }
                    for(int q=0; q<back.size(); q++) {
                        Coordinate bn = back.get(q);
                        cb[bn.y][bn.x] = '#';
                    }
                }
            }
        }
        return false;
    }
}