풀이 방법
격자판의 크기가 크지 않아서 완전탐색을 이용했다.
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);
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
팀 배정 - 18768번 (0) | 2021.11.08 |
---|---|
거짓말 - 1043번 (0) | 2021.11.08 |
Coins - 3067번 (0) | 2021.11.04 |
뱀 - 3190번 (0) | 2021.11.02 |
A -> B - 16953번 (0) | 2021.11.02 |