[BOJ 14502] 연구소

문제

• BOJ 14502
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

빈칸 중 벽을 세울 3개를 조합함수comb()를 실행하며 뽑는다.
경우의수를 뽑으면 이때 바이러스가 퍼지는 함수 go()를 실행한다.
초기 바이러스 좌표들을 담은 바이러스 리스트를 큐에 담고 하나씩 꺼내면서 바이러스가 상,하,좌,우로 퍼질수 있는지 bfs탐색을 진행한다.
이때 주의할 점은 map배열을 복사해서 바이러스를 확산시켜야 한다! 원래 배열은 항상 보존해두는것을 기억하자.
복사를 할때는 visited = map을 하게 되면 주소가 참조되므로 visited를 변경하면 map값도 변경되게 된다.
따라서 항상 2중 for문을 사용해서 각 요소의 값만을 복사하도록 한다.
큐가 빈다면 모든 바이러스 확산이 끝난 것이므로 이때의 안전영역(0인 경우)를 세서 Ans값과 비교해서 가장 최대개수만을 저장해두고 마지막에 출력해주면 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//연구소
public class Boj14502 {

	static int N, M;
	static int[][] map;
	static ArrayList<Point> virusList, nullList; // 초기 바이러스 좌표, 빈칸 좌표
	static int[] numbers, selected; //전체 인덱스 담는 배열, 뽑은 경우의 수
	static int[] di = {-1, 0, 1, 0};//상,우,하,좌
	static int[] dj = {0, 1, 0, -1}; 
	static int Ans; //답=>안전영역의 최대개수
	static Queue<Point> queue;
	static StringTokenizer st;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M]; //0번~N-1번
		virusList = new ArrayList<>();
		nullList = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				int input = Integer.parseInt(st.nextToken());
				map[i][j] = input;
				if(input == 2) virusList.add(new Point(i, j)); //바이러스 좌표
				if(input == 0) nullList.add(new Point(i, j)); //빈칸 좌표
			}
		}
		
		numbers = new int[nullList.size()]; //빈칸의 전체 인덱스를 저장할 배열
		for(int i=0; i<numbers.length; i++) numbers[i] = i;
		selected = new int[3]; //3개를 뽑은 경우의 수를 저장할 배열
		
		comb(0, 0); //안전영역 중 벽이 될 3개를 뽑자
		System.out.println(Ans);
	}

	private static void comb(int cnt, int cur) {
		if(cnt == 3) { //모두 뽑은 경우
			//배열에 표시
			int[][] tmp = new int[N][M]; //배열 복사
			for(int i=0; i<N; i++) { //tmp=map하면 안됨!!! 그럼 tmp값변경하면 map값도 변경됨!!!
				for(int j=0; j<M; j++) {
					tmp[i][j] = map[i][j];
				}
			}
			for(int i=0; i<selected.length; i++) {
				Point p = nullList.get(selected[i]);
				tmp[p.x][p.y] = 1; //벽 표시
			}
			go(tmp); //바이러스 퍼짐
			return;
		}
		
		for(int i=cur; i<numbers.length; i++) {
			selected[cnt] = numbers[i];
			comb(cnt+1, i+1);
		}
	}

  //bfs
	private static void go(int[][] tmp) {
		
		queue = new LinkedList<>(); //바이러스 좌표를 담을 큐
		for(int i=0; i<virusList.size(); i++) queue.add(virusList.get(i));
		
		while(!queue.isEmpty()) {
			int size = queue.size(); 
			
			for(int s=0; s<size; s++) { //현재 표시된 바이러스 개수만큼 진행
				Point p = queue.poll(); //바이러스 좌표 하나 꺼내서
				for(int dir=0; dir<4; dir++) { //상,우,하,좌 검색
					int ni = p.x + di[dir];
					int nj = p.y + dj[dir];
					
					if(ni >= 0 && ni < N && nj >= 0 && nj < M && tmp[ni][nj] == 0) { //범위에 안벗어나고 빈칸이면
						tmp[ni][nj] = 2; //바이러스 확산
						queue.add(new Point(ni, nj));
					}
				}
			}
		}//모든 바이러스 확산 완료
		
		
		//남은 안전영역 구하기
		int cnt = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(tmp[i][j] == 0) cnt++;
			}
		}
		
		//최대 개수가 되는 안전영역 저장하기
		Ans = Math.max(Ans, cnt);
		
	}

	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}