백준 14502 연구소 (Java)

1. 문제 링크

14502번: 연구소

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 조합을 이용해 벽을 세울 3 곳을 찾는다.

+) map을 복제하여 조합마다 결과에 영향을 미치지 않게 한다.

2. 조합으로 선택된 3 위치에 벽을 세운다.

3. 큐에 바이러스의 위치를 모두 넣어두고 사방탐색을 하면서 바이러스를 퍼뜨린다.

4. 탐색이 끝난 후 바이러스가 있는 수를 세고 최댓값일 경우 갱신한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static int N, M, map[][], clone[][], result = 0;
	static Point[] com;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static List<Point> blank, virus;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		map = new int[N][M];
		clone = new int[N][M];
		com = new Point[3];
		blank = new ArrayList<>();
		virus = new ArrayList<>();
		for(int i=0;i<N;i++) {
			split = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(split[j]);
				if(map[i][j] == 0) {
					blank.add(new Point(i, j));
				}
				else if(map[i][j] == 2) {
					virus.add(new Point(i, j));
				}
			}
		}
		
		Combination(0, 0);
		System.out.println(result);
	}
	private static void Combination(int cnt, int start) {
		if(cnt == 3) {
			//벽 세울 맵 만들기
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					clone[i][j] = map[i][j];
				}
			}
			
			//조합으로 뽑은 녀석들 벽으로 만들기
			Point temp;
			for(int i=0;i<3;i++) {
				temp = com[i];
				clone[temp.x][temp.y] = 1;
			}
			
			//일단 바이러스들은 전부 큐에 넣고 시작
			Queue<Point> queue = new ArrayDeque<>();
			for(int i=0;i<virus.size();i++) {
				temp = virus.get(i);
				queue.offer(temp);
			}
			
			while(!queue.isEmpty()) {
				temp = queue.poll();
				for(int d=0;d<4;d++) {
					int X = temp.x+dx[d];
					int Y = temp.y+dy[d];
					if(X<0 || X>=N || Y<0 || Y>=M) continue;
					if(clone[X][Y]==0) {
						clone[X][Y] = 2;
						queue.offer(new Point(X, Y));
					}
				}
			}
			
			int count = 0;
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(clone[i][j]==0) {
						count++;
					}
				}
			}
			result = Math.max(count, result);
			return;
		}
		
		for(int i=start;i<blank.size();i++) {
			com[cnt] = blank.get(i);
			Combination(cnt+1, i+1);
		}
	}
}