[BOJ] 14502 연구소 (Java)

https://www.acmicpc.net/problem/14502

알고리즘

BFS & DFS

풀이

1. DFS로 세 개의 벽을 세운다.
2. 세 개의 벽이 세워지면 BFS로 바이러스를 뿌린다.
3. 바이러스가 더 이상 뿌려지지 않는다면, 안전 구역(0)의 개수를 세서 최대값을 구한다.

코드

import java.util.*;
import java.io.*;

public class Main_14502_연구소 {

	static int N, M, answer, wallCnt, map[][];
	static int dy[] = {-1, 0, 1, 0};
	static int dx[] = {0, 1, 0, -1};
	
	static class Virus{
		int y, x;

		public Virus(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}
		
	}
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = 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());		// map 초기화
			}
		}
		
		wallCnt = 0;
		answer = 0;
		dfs(wallCnt);
		System.out.println(answer);
	}

	private static void dfs(int wallCnt) {
		// TODO Auto-generated method stub
		if(wallCnt == 3) {				// 벽이 3개 세워지면 
			bfs();					// 바이러스 뿌리기
			return;
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0) {		// 만약 벽을 세울 수 있는 공간이면
					map[i][j] = 1;		// 벽을 세우고
					dfs(wallCnt+1);		// 벽 카운트를 증가시키고 
					map[i][j] = 0;		// 다시 원래대로 되돌리고
				}				// 왜 벽을 세우고 다시 되돌리는지? => 3개의 벽이 세워지는 모든 경우를 dfs로 탐색하기 때문에 map을 원상복귀 시켜줘야 기존 맵에서 3개의 벽만 뚝딱 세워지고 바이러스가 퍼질 수 있음
			}
		}
	}

	private static void bfs() {
		// TODO Auto-generated method stub
		Queue<Virus> q = new LinkedList<>();
		int [][] copyMap = new int[N][M];
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				copyMap[i][j] = map[i][j];			// map은 전역변수라 그대로 사용하면, 매번 사용되는 맵이 바뀔 수 있으므로 벽이 3개 세워질 때마다의 맵을 복사해서 복사된 맵 사용
				if(map[i][j] == 2) q.offer(new Virus(i, j));	// 바이러스의 좌표들을 큐에 추가 
			}
		}
	
		while(!q.isEmpty()) {
			Virus curVirus = q.poll();
			for(int d=0; d<4; d++) {					// 바이러스의 4방향으로 뿌리기 시작
				int ny = curVirus.y + dy[d];
				int nx = curVirus.x + dx[d];
				if(ny>=0&&ny<N && nx>=0&&nx<M && copyMap[ny][nx]==0) {
					copyMap[ny][nx] = 2;
					q.offer(new Virus(ny, nx));		// 뻗어나갈 방향이 0인 경우에만 바이러스를 뿌리므로, 중복으로 뿌려질 경우가 없음
				}
			}
		}
		int count = 0;							// 바이러스가 다 뿌려지고 안전구역 카운트 시작 후, max값 업데이트
		for(int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				if(copyMap[i][j] == 0) count++;
			}
		}
		answer = Math.max(answer, count);
	}
}