연구소
백준 14502: 연구소
풀이
재귀함수를 사용하여 벽을 세울 3곳의 위치를 조합
- combi(int[] arr, int c, int idx, int[] sel)
- arr : 빈 칸의 위치가 들어있는 리스트의 인덱스 번호를 가지고 있는 배열
- c : 조합으로 선택되는 3곳의 벽을 담을 배열(sel)의 인덱스 번호
- idx : arr 배열의 인덱스 번호
- sel : 벽을 세울 3곳의 위치의 조합 배열
소스코드
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static class Node{
int r, c;
Node(int r, int c){
this.r = r;
this.c = c;
}
}
static int N;
static int M;
static int[][] map;
static ArrayList<Node> list;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); //지도의 세로크기
M = sc.nextInt(); //지도의 가로크기
map = new int[N][M];
list = new ArrayList<>(); //빈칸을 담을 리스트
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
map[i][j] = sc.nextInt();
if(map[i][j]==0)
list.add(new Node(i, j)); //빈칸이면 리스트에 담기
}
}
//리스트의 인덱스 번호를 arr배열에 담아서 arr배열을 가지고 조합 만들기
int[] arr = new int[list.size()];
for(int i=0; i<list.size(); i++)
arr[i]=i;
combi(arr, 0, 0, new int[3]);
System.out.println(max);
}
static int[] dr = {-1,1,0,0};
static int[] dc = {0,0,-1,1};
static int max=0;
static void combi(int[] arr, int c, int idx, int[] sel) {
if(c==sel.length) {
//3개의 조합이 나오면, 거기에 벽을 세우고 바이러스를 퍼뜨리기
int[][] copyMap = new int[N][M];
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
copyMap[i][j] = map[i][j];
}
}
for(int i=0; i<3; i++) {
int wallR = list.get(sel[i]).r; //벽을 세울 위치의 행
int wallC = list.get(sel[i]).c; //벽을 세울 위치의 열
copyMap[wallR][wallC] = 1;
}
//바이러스를 퍼뜨리는건 BFS로!!
Queue<Node> virus = new LinkedList<>(); //바이러스를 담을 큐
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(copyMap[i][j]==2)
virus.add(new Node(i, j));
}
}
while(!virus.isEmpty()) {
Node node = virus.poll();
for(int d=0; d<4; d++) {
int nr = node.r + dr[d];
int nc = node.c + dc[d];
if(nr>=0 && nc>=0 && nr<N && nc<M) {
if(copyMap[nr][nc]==0) {
virus.add(new Node(nr, nc));
copyMap[nr][nc] = 2;
}
}
}
}
//0의 개수(안전영역) 세기
int cnt = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(copyMap[i][j]==0)
cnt++;
}
}
max = Math.max(max, cnt);
return;
}
if(idx==arr.length)
return;
sel[c] = arr[idx];
combi(arr, c+1, idx+1, sel);
combi(arr, c, idx+1, sel);
}
}