https://www.acmicpc.net/problem/14502
조합
벽 3개를 놓을 수 있는 모든 경우의 수를 구해야 한다.
N*M 크기의 배열의 각 칸을 0~N*M-1까지의 번호로 가정을 하고, 해당 범위 중 3개를 고를 수 있는 조합을 만든다.
조합으로 만들어진 3개의 수 각각 i에서
i/M 은 y축, i%M은 x축으로 본다.
(i/M, i%M) 위치에 바이러스가 있으면 해당 수는 조합에 포함하지 않는다.
static void comb(int cnt, int idx) {
if (cnt == 3) {
// 다음 단계로 진행
return;
}
for (int i=idx; i<N*M; i++) {
if (arr[i/M][i%M]!=0) continue; // 해당 위치에 바이러스가 있으면 조합에 포함 x
comb[cnt] = i;
comb(cnt+1, i+1);
}
}
바이러스 확산
벽을 놓을 조합이 완성되면, 기존 배열을 복제한 후에, 각 세 위치에 벽을 놓고, 바이러스를 확산시킨다.
확산 시킨 후에 배열을 검사하여 빈 공간의 갯수만큼 세어준 후에 최댓값을 갱신한다.
static void dfs() {
ArrayDeque<int []> q = new ArrayDeque<>();
for (int [] v : virus) q.add(v);
while (!q.isEmpty()) {
int [] v = q.poll();
int y = v[0], x = v[1];
newArr[y][x] = 2;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (0<=ny&&ny<N&&0<=nx&&nx<M&&newArr[ny][nx]==0)
q.add(new int[] {ny,nx});
}
}
}
static void comb(int cnt, int idx) {
if (cnt == 3) {
for (int i=0; i<N; i++) newArr[i]=Arrays.copyOf(arr[i], M); // 배열 복제
for(int i : comb) newArr[i/M][i%M] = 1; // 각 위치에 벽 놓기
dfs(); // 바이러스 확산
int area = count(); // 빈 공간의 갯수 카운트
ans = area>ans?area:ans; // 최댓값 갱신
return;
}
for (int i=idx; i<N*M; i++) {
if (arr[i/M][i%M]!=0) continue;
comb[cnt] = i;
comb(cnt+1, i+1);
}
}
전체 코드
import java.io.*;
import java.util.*;
# public class Main {
static int N, M, ans = 0;
static int [][] arr, newArr;
static int [] comb = new int [3];
static int [] dy = {-1, 1, 0, 0};
static int [] dx = {0, 0, -1, 1};
static List <int[]> virus = new ArrayList<>();
static int count() {
int sum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (newArr[i][j]==0)sum++;
return sum;
}
static void dfs() {
ArrayDeque<int []> q = new ArrayDeque<>();
for (int [] v : virus) q.add(v);
while (!q.isEmpty()) {
int [] v = q.poll();
int y = v[0], x = v[1];
newArr[y][x] = 2;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (0<=ny&&ny<N&&0<=nx&&nx<M&&newArr[ny][nx]==0)
q.add(new int[] {ny,nx});
}
}
}
static void comb(int cnt, int idx) {
if (cnt == 3) {
for (int i=0; i<N; i++) newArr[i]=Arrays.copyOf(arr[i], M);
for(int i : comb) newArr[i/M][i%M] = 1;
dfs();
int area = count();
ans = area>ans?area:ans;
return;
}
for (int i=idx; i<N*M; i++) {
if (arr[i/M][i%M]!=0) continue;
comb[cnt] = i;
comb(cnt+1, i+1);
}
}
public static void main(String[] args) throws Exception {
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 int [N][M];
newArr = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 2) virus.add(new int[] {i, j});
}
}
comb(0, 0);
br.close();
System.out.println(ans);
}
}