백준 JAVA) 14502번 문제 연구소

일단 문제를 볼까요?

www.acmicpc.net/problem/14502

14502번: 연구소

저는 자바로 구현해보았습니다.

import java.util.Scanner;
public class Main {
	
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	static int N,M, an;
	static int[][] temp, map;
	
	static void wall(int v, int cnt) {	
		if(cnt ==3) {
			temp = new int[N][M];
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					temp[i][j] = map[i][j];
				}
			}
			
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(temp[i][j] ==2) {
						speed(i,j);
					}
				}
			}
			safe();
		}else {
			for(int i= v+1;i<N*M;i++) {
				int ny = (int)i /M;
				int nx = i%M;
				if(map[ny][nx] == 0) {
					map[ny][nx] =1;
					wall(i,cnt+1);
					map[ny][nx]=0;
				}
			}
		}	
	}
	
	static void speed(int y, int x) {
		for(int k=0;k<4;k++) {
			int ny = dy[k]+y;
			int nx = dx[k]+x;
			
			if(ny >= 0 && ny < N && nx >= 0 && nx < M) {
                if (temp[ny][nx] == 0) {
                    temp[ny][nx] = 3;
                    speed(ny, nx);
                }
			}
		}
	}
	
	static void safe() {
		int safet =0;
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(temp[i][j] ==0) {
					++safet;
				}
			}
		}
		if(safet>an) {
			an = safet;
		}
	}
	
	
	
	
	public static void main(String[] arg) {
		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		M = scanner.nextInt();
		
		map = new int[N][M];
		
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<M;j++) {
				map[i][j]= scanner.nextInt();
			}
		}
		
		for(int i=0;i<N*M;i++) {
			int ny =(int) i / M;
			int nx = i %M;
			
			if(map[ny][nx] == 0) {
				map[ny][nx]=1;
				wall(i,1);
				
				map[ny][nx]=0;
			}
		}
		System.out.println(an);
		
		
		}
	}

2차원 배열로 구현해서 상하 좌우에 바이러스가 퍼지는 것을 막기위해 벽을 3개를 최적화된 곳에 세워주는 문제입니다.