연구소


백준 14502: 연구소

문제보기
Alt text

풀이

재귀함수를 사용하여 벽을 세울 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);
	}
}