[완전탐색, DFS] BOJ_14502 연구소 "JAVA"

🚀링크

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

💻문제

🌏문제풀이

주석참고

👩‍💻코드

package javaTest;

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

//virus의 위치를 저장하기 위한 class
class virusPoint {
	int row;
	int col;
	
	public virusPoint(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

public class BOJ_14502 {
	static ArrayList<virusPoint> virusList;
	static int N, M, max;
	static int[][] map; //입력받는 맵
	static int[][] wall; //벽을 놓을 맵
	//상하좌우로 한칸씩 이동하기 위함
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};

	//완전탐색을 위해 맵은 카피하여 사용
	public static int[][] copy(int[][] arr){
		int[][] copy = new int[N][M];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				copy[i][j] = arr[i][j];
			}
		}
		
		return copy;
	}
	
	//벽을 세우는 함수
	public static void makeWall(int depth) {
		//벽 3개를 다 세우는 경우 바이러스를 퍼트린다
		if(depth == 3){
			spreadVirus();
			return;
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(wall[i][j] == 0) { //빈칸인 경우
					wall[i][j] = 1; //벽으로 막아주고
					makeWall(depth+1); //진행시킴
					wall[i][j] = 0; //완전탐색을 위해 원복
				} 
			}
		}
	}
	
	//상하좌우로 이동한 값이 배열의 범위를 벗어나지 않는지 체크
	public static boolean isValid(int row, int col) {
		if(row < 0 || row >= N || col < 0 || col >= M)
			return false;
		return true;
	}
	
	//바이러스를 퍼트리는 함수
	public static void spreadVirus() {
		//벽을 세운 오리지널 wall 배열에 영향을 주지 않기 위해 copy
		int[][] copyWall = copy(wall);
		
		//바이러스를 담는 과정
		Queue<virusPoint> vq = new LinkedList<virusPoint>();
		for(int i=0; i<virusList.size(); i++) {
			//virusList 내 virusPoint class 형태로 가져옴
			vq.offer(new virusPoint(virusList.get(i).row, virusList.get(i).col));
		}
		
		//전염 시작
		while(!vq.isEmpty()) {
			int row = vq.peek().row;
			int col = vq.poll().col;
			
			//상하좌우로 이동
			for(int k=0; k<4; k++) {
				int nextRow = row+dx[k]; //dy로 바꿔도 값엔 변화 없음
				int nextCol = col+dy[k];
				
				//이동한 값이 유효하고 0이면 바이러스를 퍼트림
				if(isValid(nextRow, nextCol) && copyWall[nextRow][nextCol] == 0) {
					copyWall[nextRow][nextCol] = 2;
					//새로운 바이러스가 생겼으므로 큐에 삽입
					vq.offer(new virusPoint(nextRow, nextCol));
				}
			}
		}
		//안전지역 수 구함
		int sc = countSafe(copyWall);
		max = Math.max(max, sc);
	}
	
	public static int countSafe(int[][] copyWall) {
		int sc = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(copyWall[i][j] == 0)
					sc = sc + 1;
			}
		}
		return sc;
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine());
		virusList = new ArrayList<virusPoint>();
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		max = 0;
		
		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());
				//map에 값을 넣으면서 바이러스가 존재하면 해당 위치를 저장
				if(map[i][j] == 2) {
					virusList.add(new virusPoint(i,j));
				}
			}
		}
		
		//오리지널 맵 카피
		wall = copy(map);
		
		makeWall(0);
		
		System.out.println(max);
	}

}