[백준] 14502번 연구소

 연구소에 바이러스가 퍼지지 못하게 3개의 기둥을 세워서 피해를 최소한으로 만드는 알고리즘 문제 입니다. 탐색(BFS, DFS)에대해서 공부해야겠다는 생각을 갖도록 만들었던 문제 입니다. 처음에는 어떻게 접근해야할지 감도 못잡았는데 탐색에대해 공부하니 어렵지 않게 풀 수 있었습니다. 아래는 문제의 링크 입니다.

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

 3개의 기둥을 세우는 방법은 재귀 함수를 만들어서 해결 했습니다. 3개의 기둥이 모두 세워졌을때 BFS탐색을 이용해서 벽이 아닌 곳으로 바이러스를 퍼뜨렸습니다. 그리고 바이러스가 퍼진 연구소를 다시 원상 복귀 시키며 바이러스가 퍼지지 않은 부분을 계산하였습니다. 문제를 풀면서 아쉬웠던 부분은 기둥을 세우는 부분의 재귀 함수를 조금 더 깔끔하게 코딩할 수 있지 않았을까 하는 아쉬움이 남았습니다. 아래는 완성된 코드 입니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class VirusLab {
	
	static final int WALL_NUM_LIMIT = 3;
	static final int VIRUS_NUM_LIMIT = 3;
	
	int[][] originalMap, copyMap;
	int row, col;
	int[] dRow = {0,0,-1,1}, dCol = {-1,1,0,0};
	int cntWall = 0;
	ArrayList<Pair<Integer, Integer>> virusPair;
	ArrayList<Pair<Integer, Integer>> wallPair;
	int maxSafeZone = 0;
	
	void recoveryMap(){
		int tempNum = 0;
		for(int i=0;i<row;i++){
			for(int j=0;j<col;j++){
				if(copyMap[i][j] == 0){
					tempNum++;
				}
				copyMap[i][j] = originalMap[i][j];
			}
		}
		
		if(tempNum > maxSafeZone){
			maxSafeZone = tempNum;
		}
		
	}
	
	void spreadVirusBfs(){
		Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>();
		int qRow, qCol;
		int nRow, nCol;
		int tempRow, tempCol;
		Pair<Integer, Integer> tempPair;
		
		for(int i=0;i<virusPair.size();i++){
			q.add(virusPair.get(i));
		}
		
		for(int i=0;i<wallPair.size();i++){
			tempRow = wallPair.get(i).x;
			tempCol = wallPair.get(i).y;
			copyMap[tempRow][tempCol] = 1;
		}
		
		while(!q.isEmpty()){
			tempPair = q.poll();
			qRow = tempPair.x;
			qCol = tempPair.y;
			
			for(int i=0;i<4;i++){
				nRow = qRow + dRow[i];
				nCol = qCol + dCol[i];
				if(0 <= nRow && nRow < row && 0 <= nCol && nCol < col){
					if(copyMap[nRow][nCol] == 0){
						copyMap[nRow][nCol] = 2;
						tempPair = new Pair<Integer, Integer>(nRow, nCol);
						q.add(tempPair);
					}
				}
			}
		}
		
		recoveryMap();
		
	}
	
	void makeWall(int rowVal, int colVal){
		if(cntWall == WALL_NUM_LIMIT){
			spreadVirusBfs();
		}else{
			for(int i=rowVal;i<row;i++){
				for(int j=colVal;j<col;j++){
					if(j+1 >= col){
						colVal = 0;
					}
					if(copyMap[i][j] == 0){
						wallPair.add(new Pair<Integer, Integer>(i,j));
						copyMap[i][j] = 1;
						cntWall++;
						makeWall(i,j);
						cntWall--;
						copyMap[i][j] = 0;
						wallPair.remove(cntWall);
					}
				}				
			}
		}
		
	}
	
	void solution(){
		Scanner s = new Scanner(System.in);
		virusPair = new ArrayList<Pair<Integer, Integer>>();
		wallPair = new ArrayList<Pair<Integer, Integer>>(); 
		
		row = s.nextInt();
		col = s.nextInt();
		originalMap = new int[row][col];
		copyMap = new int[row][col];
		
		for(int i=0;i<row;i++){
			for(int j=0;j<col;j++){
				originalMap[i][j] = s.nextInt();
				copyMap[i][j] = originalMap[i][j];
				if(originalMap[i][j] == 2){
					virusPair.add(new Pair<Integer, Integer>(i,j)); 
				}
			}
		}
		
		for(int i=0;i<row;i++){
			for(int j=0;j<col;j++){
				if(copyMap[i][j] == 0){
					cntWall++;
					wallPair.add(new Pair<Integer, Integer>(i,j));
					copyMap[i][j] = 1;
					makeWall(i,j);
					cntWall--;
					copyMap[i][j] = 0;
					wallPair.remove(cntWall);
				}
			}
		}
		
		System.out.println(maxSafeZone);
		
	}

	public static void main(String[] args) {
		VirusLab m = new VirusLab();
		m.solution();
		
	}
	
	class Pair<X, Y>{
		X x;
		Y y;
		
		public Pair(X x, Y y){
			this.x = x;
			this.y = y;
			
		}
		
	}

}