[백준] 14502. 연구소(골드5)

백준(골드5) - 14502. 연구소(골드5)

---

---

풀이

dfs와 bfs를 둘다 사용하는 문제였다.
우선 벽을 세울 수 있는 곳에 벽 3개를 설치한다. 다만 다 설치하고 난 뒤 돌아올때는 해당 벽을 다시 돌려놓아야 한다.
벽 3개를 다 설치하면 바이러스가 상하좌우로 인접한 빈칸으로 모두 퍼져나간다. => virus();

private static void dfs(int wall) {
		if(wall == 3) {
			virus();
			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(wall+1);
					map[i][j] = 0;//벽 설치 원래대로 돌아오게 한다.
				}
			}
		}
	}

바이러스는 bfs를 이용해서 풀었다. queue에 확산하기 전의 바이러스들의 위치를 모두 넣는다. 그리고 while을 이용해서 상하좌우에 바이러스를 전파시키고, 전파된 바이러스들의 위치를 queue에 넣어준다. 해당 로직은 큐가 비어있지 않을때까지 반복한다.

private static void virus() {
		Queue<Virus> queue = new LinkedList<Virus>();
		int temp[][] = new int[n][m];
		
		//map copy && virus 위치 저장
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				temp[i][j] = map[i][j];
				if(temp[i][j] == 2) {
					queue.offer(new Virus(i,j));
				}
			}
		}
		
		//virus 확산
		while(!queue.isEmpty()) {
			Virus current = queue.poll();
			int x = current.x;
			int y = current.y;
			
			for(int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(isValid(nx,ny) && temp[nx][ny] == 0) {
					temp[nx][ny] = 2;
					queue.offer(new Virus(nx,ny));
				}
			}	
		}
		safeArea(temp);
	}

총 코드

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

public class Main {
	static int[] dx = {-1,1,0,0};//상하좌우
	static int[] dy = {0,0,-1,1};
	static class Virus{
		int x;
		int y;
		Virus(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	static int n,m,max;
	static int[][] map;
	public static void main(String[] args) throws Exception {
		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];
		max = Integer.MIN_VALUE;
		
		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());
				
			}
		}
		
		// 벽 세우는 함수
		dfs(0);
		System.out.println(max);
	}
	
	private static void dfs(int wall) {
		if(wall == 3) {
			virus();
			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(wall+1);
					map[i][j] = 0;//돌려놔
				}
			}
		}
	}
	
	private static void safeArea(int[][] temp) {//0을 count
		int count = 0;
		for(int i=0; i<n; i++) {//입력
			for(int j=0; j<m; j++) {
				if(temp[i][j] == 0) count++;
			}
		}
		max = Math.max(max, count);
	}
	
	private static void virus() {
		Queue<Virus> queue = new LinkedList<Virus>();
		int temp[][] = new int[n][m];
		
		//map copy && virus 위치 저장
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				temp[i][j] = map[i][j];
				if(temp[i][j] == 2) {
					queue.offer(new Virus(i,j));
				}
			}
		}
		
		//virus 확산
		while(!queue.isEmpty()) {
			Virus current = queue.poll();
			int x = current.x;
			int y = current.y;
			
			for(int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(isValid(nx,ny) && temp[nx][ny] == 0) {
					temp[nx][ny] = 2;
					queue.offer(new Virus(nx,ny));
				}
			}	
		}
		safeArea(temp);
	}
	
	private static boolean isValid(int x, int y) {
		if(x>=0 && y>=0 && x<n && y<m) return true;
		return false;
	}
}