[백준/14502/Java] 연구소

 

문제:

www.acmicpc.net/problem/14502

14502번: 연구소

 

먼저 문제를 풀고 오시는 것을 추천드립니다.

 

 

문제분석

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었습니다.

다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 합니다.

 

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있습니다.

연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지합니다.

 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있습니다.

새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 합니다.

 

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어집니다. (3 <= N, M <= 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어집니다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치입니다.

2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수입니다.

빈 칸의 개수는 3개 이상입니다.

 

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력합니다.

 

 

풀이

먼저 바이러스를 확산하는 것은 BFS로 할 수 있습니다.

그리고 확산 후에 안전영역을 세는 것은 지도의 모든 영역을 조사해서 0의 개수를 구하면 됩니다.

 

아무래도 가장 문제가 되는 것은 벽을 3개 세우는 것일 듯 합니다.

벽은 빈 칸에 세워야 합니다.

따라서, 빈 칸 중 하나에 벽을 세우고, 남은 빈 칸들 중에서 2번째 벽을 세우고, 또 남은 빈 칸들 중에서 3번째 벽을 세웁니다. 3번째 벽을 세우면 바이러스 확산하고 안전영역의 크기를 구합니다.

그리고 3번째 벽을 허물고 다음 빈 칸에 3번째 벽을 세우고 바이러스 확산 및 안전영역의 크기를 구합니다.

이걸 반복하면 됩니다. 즉, 조합으로 풀 수 있으므로 DFS로 풀어보도록 하겠습니다.

 

예제 풀이

문제에 있는 첫번째 예제는 지도가 좀 커서 2번째 예제를 먼저 보도록 하겠습니다.

 

초기값

 

벽 3개를 세우는 몇 가지 케이스를 보도록 하겠습니다.

벽을 세운 칸을 노란색으로 표시하였습니다.

바이러스 확산 후 안전영역은 파란색으로 표시하였습니다.

 

안전영역 1개

이렇게 벽을 세우면 1개의 안전영역이 생깁니다.

 

안전영역 4개

(0, 0) 위치의 벽을 유지한 상태에서 2번째, 3번째 벽을 다른 위치에 세운 경우입니다.

 

안전영역 8개

바로 위 지도에서 (0, 0) 벽을 (3, 3) 위치에 세운 경우입니다.

 

 

안전영역 9개

(0, 3) 벽을 (0, 4) 위치로 한 칸 이동한 경우입니다.

이 경우가 안전영역 크기가 가장 최대인 경우입니다.

 

 

 

소스

지도 정보는 2차원 배열 A에 저장합니다.

A 배열에서 dfs로 벽 3개를 설치합니다.

 

바이러스를 확산하고 다시 원래대로 바이러스 확산 전 상태로 원복하기 좀 불편하기 때문에

동일한 크기의 2차원 배열 B를 선언하여 바이러스를 확산하고 안전영역 크기를 셉니다.

 

벽을 모든 빈 칸에 세워야 하므로 2차원 배열 모든 값을 조사하면서 

빈 칸이면 dfs로 벽을 하나씩 세우기 시작합니다.

따라서, dfs 함수에 i 위치, j 위치, 몇 번째 벽인지 count를 세서 파라미터로 넘겨줍니다.

private static void dfs(int a, int b, int cnt)

 

dfs로 벽을 세우다가 cnt 값이 3이 되면 

1. copy 함수로 A 배열의 값을 B 배열로 복사합니다.

2. virus 함수로 BFS를 이용하여 바이러스를 확산합니다.

3. safety 함수로 안전영역의 크기를 계산하고 가장 큰 값이면 ANS 변수에 저장합니다.

 

모든 탐색이 끝나면 ANS 변수를 출력합니다.

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

public class Main {
	static int N, M;
	static int A[][];
	static int B[][];
	static int visited[][];
	
	static int ANS = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());
		
		A = new int[N][M];
		B = new int[N][M];
		visited = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				A[i][j] = Integer.valueOf(st.nextToken());
				B[i][j] = A[i][j];
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (A[i][j] == 0 && visited[i][j] == 0)
				{
					visited[i][j] = 1;
					A[i][j] = 1;
					dfs(i, j, 1);
					visited[i][j] = 0;
					A[i][j] = 0;
				}
			}
		}
		
		System.out.println(ANS);
	}

	private static void dfs(int a, int b, int cnt) {
		if (cnt == 3)
		{
			copy();
			virus();
			safety();
			return;
		}
		
		for (int i = a; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (A[i][j] == 0 && visited[i][j] == 0)
				{
					visited[i][j] = 1;
					A[i][j] = 1;
					dfs(i, j, cnt+1);
					visited[i][j] = 0;
					A[i][j] = 0;
				}
			}
		}
	}

	private static void copy() {
		for (int k = 0; k < N; k++) {
			B[k] = Arrays.copyOf(A[k], M);
		}
	}

	private static void virus() {
		visited = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (B[i][j] == 2)
				{
					bfs(i, j);
				}
			}
		}
	}

	private static void bfs(int i, int j) {
		Queue<Integer> q = new LinkedList<Integer>();
				
		q.add(i * 100 + j);
		
		while (q.isEmpty() == false)
		{
			int n = q.remove();
			i = n / 100;
			j = n % 100;
			
			if (i-1>=0 && B[i-1][j] == 0)
			{
				B[i-1][j] = 2;
				q.add((i-1)*100 + j);
			}
			if (i+1 < N && B[i+1][j] == 0)
			{
				B[i+1][j] = 2;
				q.add((i+1)*100 + j);
			}
			if (j-1>=0 && B[i][j-1] == 0)
			{
				B[i][j-1] = 2;
				q.add(i*100 + (j-1));
			}
			if (j+1<M && B[i][j+1] == 0)
			{
				B[i][j+1] = 2;
				q.add(i*100 + (j+1));
			}
		}
	}

	private static void safety() {
		int count = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (B[i][j] == 0)
				{
					count++;
				}
			}
		}
		
//		ANS = Math.max(ANS, count);
		if (ANS < count)
		{
			ANS = count;
//			System.out.println(ANS);
//			for (int i = 0; i < N; i++) {
//				System.out.println(Arrays.toString(B[i]));
//			}
		}
	}
}