십자가 2개 놓기 - 17085번

---

풀이 방법

격자판의 크기가 크지 않아서 완전탐색을 이용했다.

max값을 만들 수 있는 모든 십자가의 넓이를 비교해서 max 값을 처음 정해서 넓이가 1인 경우는 제외했다.

list에 만들 수 있는 십자가가 차이자는 위치를 넣어주고 십자가가 겹치지 않는 경우에 넓이 곱의 최댓값을 구해주었다.

 

내 코드

package com.company;

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

public class Main {
    static int N, M;
    static String[][] arr;
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();

    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());

        arr = new String[N + 2][M + 2];

        for (int i = 0; i < N + 2; i++) {
            Arrays.fill(arr[i], ".");
        }

        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            for (int j = 1; j <= M; j++) {
                arr[i][j] = s.charAt(j - 1) + "";
            }
        }

        int index = -1;
        int max = 1;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr[i][j].equals("."))
                    continue;
                int x = 1;

                while (true) {
                    if (arr[i + x][j].equals("#")
                            && arr[i - x][j].equals("#")
                            && arr[i][j + x].equals("#")
                            && arr[i][j - x].equals("#")) {
                        list.add(new ArrayList<>());
                        index++;
                        list.get(index).add(new int[]{i, j});

                        for (int k = 1; k <= x; k++) {
                            list.get(index).add(new int[]{i + k, j});
                            list.get(index).add(new int[]{i - k, j});
                            list.get(index).add(new int[]{i, j + k});
                            list.get(index).add(new int[]{i, j - k});
                        }
                        max = Math.max(list.get(index).size(), max);
                        x++;
                    } else break;
                }
            }
        }

        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                boolean check = true;

                for (int k = 0; k < list.get(i).size(); k++) {
                    for (int v = 0; v < list.get(j).size(); v++) {
                        if(list.get(i).get(k)[0] == list.get(j).get(v)[0]
                                && list.get(i).get(k)[1] == list.get(j).get(v)[1]){
                            check = false;
                            break;
                        }
                    }
                    if(!check)
                        break;
                }

                if(check)
                    max = Math.max(list.get(i).size() * list.get(j).size(), max);
            }
        }
        System.out.println(max);
    }
}