본문 바로가기
백준

백준 14502번 : 연구소

by Huiyeong 2021. 4. 5.

 문제

www.acmicpc.net/problem/14502

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

14502 연구소

 

 

 

 구현 방법

 벽 3개를 세울 수 있는 모든 경우의 수를 구해야합니다.

미리 빈칸의 개수와 좌표를 저장해두어 빈칸 중 3개를 구하여 구할 때마다 dfs를 돌려 바이러스를 퍼트려줍니다.

바이러스가 적게 퍼져야 안전영역이 커지므로 바이러스가 퍼지는 개수를 구해주어 이들의 최솟값을 구하여 안전영역의 최댓값을 구해줍니다.

 

 구현 코드

package BOJ.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ14502_연구소 {
	static int R, C, MIN, danger;
	static int[] select;
	static int[][] lab, deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static boolean[][] visited;
	static List<Move> blank, virus;
	static class Move {
		int r, c;

		public Move(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		lab = new int[R][C];
		blank = new ArrayList<>();
		virus = new ArrayList<>();
		int blankCnt = 0;
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<C;c++) {
				lab[r][c] = Integer.parseInt(st.nextToken());
				if (lab[r][c]==2) virus.add(new Move(r, c)); // 바이러스 저장
				else if (lab[r][c]==0) { // 빈칸일 때
					blankCnt++; // 빈칸 개수 세어주기
					blank.add(new Move(r, c)); // 빈칸 저장
				}
			}
		}
		// 입력완료
		select = new int[3]; 
		MIN = Integer.MAX_VALUE;
		combination(0, 0); // 조합 구하기
		int labSize = blankCnt-3-MIN+virus.size(); // 빈칸의 개수 - 벽 3개 - 바이러스 퍼진 구간 + 중복된 바이러스 개수
		System.out.println(labSize);
	}
	
	static void combination(int cnt, int start) {
		if (cnt==3) { // 3개 고르면
			visited = new boolean[R][C];
			
			for (int i=0;i<3;i++) {
				int r = blank.get(select[i]).r;
				int c = blank.get(select[i]).c;
				visited[r][c] = true; // 선택된 빈칸 3개 좌표 방문처리
			}
			
			danger = 0;
			for (int r=0;r<R;r++) {
				for (int c=0;c<C;c++) {
					if (!visited[r][c] && lab[r][c] == 2) { // 바이러스 퍼져라!!
						dfs(r, c);
					}
				}
			}
			MIN = Math.min(MIN, danger); // 최솟값 구하기 (바이러스가 제일 적게 퍼져야 안전영역이 커짐)
			return;
		}
		
		for (int i=start;i<blank.size();i++) { // 크기가 3 조합구하기
			select[cnt] = i;
			combination(cnt+1, start+1);
		}
	}
	
	static void dfs(int r, int c) {
		if (MIN<danger) return; // 최솟값보다 커지면 그만 구하기
		danger++;
		for (int d=0;d<4;d++) {
			int nr = r+deltas[d][0];
			int nc = c+deltas[d][1];
			if (isIn(nr, nc) && !visited[nr][nc] && lab[nr][nc] ==0) {
				visited[nr][nc] = true;
				dfs(nr, nc);
			}
		}
		
		return;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!