[BaekJoon] 백준 14502번 연구소

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

14502번: 연구소

 

초기에 존재하는 빈칸에 대해 3개의 벽을 세울 수 있는 방법으로 dfs를 사용해서 벽을 세우고

3개의 벽을 세웠다면 바이러스의 전파를 계산하고 남아있는 0을 카운트한다.

 

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

public class Main {
	static int MAX = 0;
	static int N;
	static int M;
	static ArrayList<Point> empty;
	static ArrayList<Point> virus;
	
	static class Point {
		int i;
		int j;
		public Point(int i, int j) {
			this.i = i; this.j = j;
		}
	}
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String[] str = br.readLine().split(" ");
			N = Integer.parseInt(str[0]);
			M = Integer.parseInt(str[1]);
			int[][] room = new int[N][M];
			empty = new ArrayList<>();
			virus = new ArrayList<>();
			
			for(int i = 0; i<N; i++) {
				String[] s = br.readLine().split(" ");
				for(int j = 0; j<M; j++) {
					room[i][j] = Integer.parseInt(s[j]);
					if(room[i][j] == 0) {
						empty.add(new Point(i, j));
					}
					if(room[i][j] == 2)
						virus.add(new Point(i, j));
				}
			}
			func(0, room, 0);
			System.out.println(MAX);
		}catch(IOException e) {	
		}
	}
	
	public static void func(int count, int[][] room, int index) {
		if(count == 3) {
			//TODO: Calculate room
			int total = 0;
			int[][] result = DeepCopy(room);
			result = spreadVirus(result);
			for(int i = 0; i<N; i++) {
				for(int j = 0; j<M; j++) {
					if(result[i][j] == 0)
						total++;
				}
			}
			if(MAX < total)
				MAX = total;
			return;
		}
		if(index >= empty.size() || count > 3)
			return;
		else {
			int[][] r = DeepCopy(room);
			Point p = empty.get(index);
			func(count, r, index+1);			//선택 안했을 때
			
			r[p.i][p.j] = 1;
			func(count+1, r, index+1); 			//벽 선택했을 때
		}
	}
	
	public static int[][] DeepCopy(int[][] target) {
		int[][] result = new int[N][M];
		for(int i = 0; i<N; i++) {
			System.arraycopy(target[i],  0,  result[i],  0,  M);
		}
		
		return result;
	}
	public static int[][] spreadVirus(int[][] room) {
		Stack<Point> stack = new Stack();
		for(int i = 0; i<virus.size(); i++) {
			stack.push(virus.get(i));
		}
		
		while(!stack.isEmpty()) {
			Point p = stack.pop();
			if(p.i > 0) {
				if(room[p.i-1][p.j] == 0) {
					room[p.i-1][p.j] = 2;
					stack.push(new Point(p.i-1, p.j));
				}
			}
			if(p.i < N-1) {
				if(room[p.i+1][p.j] == 0) {
					room[p.i+1][p.j] = 2;
					stack.push(new Point(p.i+1, p.j));
				}
			}
			if(p.j > 0) {
				if(room[p.i][p.j-1] == 0) {
					room[p.i][p.j-1] = 2;
					stack.push(new Point(p.i, p.j-1));
				}
			}
			if(p.j < M-1) {
				if(room[p.i][p.j+1] == 0) {
					room[p.i][p.j+1] = 2;
					stack.push(new Point(p.i, p.j+1));
				}
			}
		}
		return room;
	}
	
}