[Java] BOJ 14502번 연구소

14502번: 연구소

---

풀이

DFS를 사용해서 벽을 둘 수 있는 모든 경우를 조사하고 벽 3개를 모두 세웠다면 배열을 복사한 후 DFS를 이용하여 바이러스를 퍼트리게 했습니다.

다음으로 DFS가 끝나면 바이러스가 퍼지지 않은 영역을 조사해서 안정 영역의 최댓값을 갱신하게 하여 해결했습니다.

---

코드

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

public class Main {
	public static int N, M, answer;
	public static int[][] map, copyMap;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		copyMap = new int[N][M];
		
		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		go(0, 0, 0);
		
		System.out.println(answer);
	}
	
	public static void go(int y, int x, int cnt) {
		if (cnt == 3) {
			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 < N; ++i) {
				for (int j = 0; j < M; ++j) {
					if (copyMap[i][j] == 2) {
						dfs(i, j);
					}
				}
			}
			
			// 안전영역 찾기
			int saftCnt = 0;
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < M; ++j) {
					if (copyMap[i][j] == 0) {
						saftCnt++;
					}
				}
			}
			
			// 정답 갱신
			answer = (answer < saftCnt) ? saftCnt : answer;
			
			return;
		}
		
		if (y == N) {
			return;
		}
		
		if (x == M) {
			go(y + 1, 0, cnt);
			return;
		}
		
		if (map[y][x] == 0) {
			// 1로 바꾸는 경우
			map[y][x] = 1;
			go(y, x + 1, cnt + 1);
			// 1로 안바꾸는 경우
			map[y][x] = 0;
		}
		
		go(y, x + 1, cnt);
	}
	
	public static int[] dx = {0, 0, -1, 1};
	public static int[] dy = {-1, 1, 0, 0};
	
	public static void dfs(int y, int x) {
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) {
				continue;
			}
			
			if (copyMap[ny][nx] == 0) {
				copyMap[ny][nx] = 2;
				dfs(ny, nx);
			}
		}
	}
}

---

pyo7410/Algorithm