14502 연구소

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

class Position{
	
	int x;
	int y;
	
	Position(int x, int y) {
		this.x = x;
		this.y = y;
	}	
}

public class Main {	
	
	
	static int N;
	static int M;
	static int input[][];
	static int input2[][];
	static int max_count;	
	static ArrayList<Position> list;
	
	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());
		input= new int[N][M];
		input2 = new int[N][M];
		list = new ArrayList<>();
		max_count =Integer.MIN_VALUE;
	
		for(int i=0; i<N; i++) {
			st= new StringTokenizer(br.readLine(), " " );
			for(int j= 0; j<M; j++) {
				
				int value = Integer.parseInt(st.nextToken());
				input[i][j] = value;
				
				if(value ==2) {
					list.add(new Position(i,j));
				}	
				
			}
		}			
			makeWall(0);					
			System.out.println(max_count);		
			
	}
	
	// 바이러스 퍼뜨리기
	public static void spreadVirus() {
		
		Queue<Position> queue = new LinkedList<>();
		
		for(int i=0; i<list.size(); i++) {			
			queue.add(list.get(i));
		}
		
		while(!queue.isEmpty()) {
		
			Position p = queue.poll();
			int x = p.x;
			int y = p.y;		
			
			int dx[] = {-1,1,0,0};
			int dy[] = {0,0,-1,1};
			
			
			for(int i =0; i<4; i++) {
				
				
				int nextX = x + dx[i];
				int nextY = y + dy[i];
				
				
				if(nextX>=0 && nextX<N && nextY >=0 && nextY<M && input2[nextX][nextY]==0) {
					
					input2[nextX][nextY] =2;
					queue.add(new Position(nextX, nextY));
									
				}				
			}
		}		
		
		int count = 0;
		
		for(int i=0; i<N; i++) {
			for(int j = 0; j<M; j++) {
				
				if(input2[i][j]==0) {
					count++;					
				}
			}
		}
		
		max_count = Math.max(count, max_count);		
	}
	
	// 배열 깊은 복사 
	public static int[][] makeArray(int a[][]) {
		
		int b [][] = new int[N][M];
		
		for(int i=0;i<b.length; i++) {
			System.arraycopy(a[i],0, b[i],0,a[0].length);
		}		
		return b;
	}
	
	
	// 벽 만들기 
	public static void makeWall(int depth) {
		
		if(depth==3) {
			
			input2 = makeArray(input);
			spreadVirus();			
			return;			
		}
		
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				
				if(input[i][j] == 0) {
					
					input[i][j] = 1;
					makeWall(depth+1);					
					input[i][j] = 0;
					
				}				
			}
		}		
	}
}

 

 

 

참고 블로그 :https://minhamina.tistory.com/69

[백준 - Java] 14502번 : 연구소 (삼성 SW 역량 테스트 기출 문제)

 

* 주의할 점 : 배열 깊은 복사, 얕은 복사