[백준-14052] 연구소

이 문제는 백준 골드 5 레벨의 문제이다. 

 

처음에는 어떻게 풀어야 할 지 감도 안오고 막막했는데, 단계를 하나씩 나누어서 생각해 보았다.

 

1) 벽은 무조건 3개를 놓아야 하니까, 벽을 설치할 3곳 찾기.

2) 벽 설치할 곳 찾았으면 벽 설치. map에서 벽 부분 1로 바꿔주기 (순열 짜는 코드 이용)

3) 바이러스 퍼트리기 (bfs 이용, 바이러스가 갈 수 있는 모든 곳에 다 보내기)

4) 안전영역 세주기

5) 다음 번을 설치해 주기 위해 원상복구 시키기.

 

이 과정을 완전탐색으로 반복했다. 

원래는 혼자서 bfs 짜는 법도 몰랐는데 조금씩 늘어가고 있는 것 같다.

갈 길이 아직 멀긴 하지만, 천천히 하다보면 조금씩 늘겠지 뭐..

 

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

public class 연구소_14502 {
	static int N,M;
	static int[][] map;
	static int[][] copy;
	static Point[] wall;
	static boolean[][] check;
	static int ans;
	
	static int[] dr = {-1,1,0,0}; //상하좌우 
	static int[] dc = {0,0,-1,1};
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		copy = new int[N][M];
		wall = new Point[3];
		check = new boolean[N][M];
		
		for(int i=0; i<N; i++) { //입력
			for(int j=0; j<M; j++) {
				map[i][j] = sc.nextInt();
				copy[i][j] = map[i][j];
			}
		}
		
		build(0);
		
		System.out.println(ans);
		
	}
	static void build(int cnt){ //벽 세우기 함수
		//자 이제 벽을 놓아보자. 아무데나 다 놓을까.. 
		if(cnt == 3) {
			walls(); //이번에 나온 벽 설치
			spread(); //벽 3개 다 설치 했으니 바이러스 퍼트리기
			count(); //안전영역 세주기
			back(); //원상복구
			return;
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				//빈칸이고, 벽 세운적 없고, 세울 수 있다면
				if(map[i][j] == 0 && !check[i][j] && cnt < 3) {
					check[i][j] = true;
					wall[cnt] = new Point(i,j);
					build(cnt+1);
					check[i][j] = false;
				}
			}
		}
		
	}
	
	static void walls() {
		for(int k=0; k<3; k++) {			
			out: for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(wall[k].r == i && wall[k].c == j){
						map[i][j] = 1;
						break out;
					}
				}
			}
		}
	}
	
	static void back() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j] = copy[i][j];
			}
		}
	}
	
	static void spread(){ //2를 퍼뜨려줄 함수
		Queue<Point> q = new LinkedList<>();
		boolean[][] visited = new boolean[N][M];
		//기존에 존재하는 바이러스 싹 다 넣어줌.
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 2) {
					q.add(new Point(i,j));
					visited[i][j] = true;
				}
			}
		}
		
		//큐가 끝나면 바이러스가 갈 수 있는 모든 길 다 간 것.
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			for(int i=0; i<4; i++) {
				int nr = p.r + dr[i];
				int nc = p.c + dc[i];
				//칸 넘어가면 pass
				if(nr<0 || nc<0 || nr>=N || nc>=M)
					continue;
				//방문 한 적 있거나 벽이면 pass
				if(visited[nr][nc] && map[nr][nc] == 1)
					continue;
				//빈 칸을 만나면 방문한 적 있다고 체크하고 바이러스 감염시킴.
				if(map[nr][nc] == 0){
					visited[nr][nc] = true;
					map[nr][nc] = 2;
					q.add(new Point(nr,nc));
				}
			}
		}
	}
	
	static void count() { //안전영역 세 줄 함수
		int cnt = 0;
		//map에 0이 몇 개 있는지 세 주기.
		//어차피 벽 놓아보고 바이러스 퍼트리고 셀거라 그냥 세줘도 ㄱㅊ
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0)
					cnt++;
			}
		}
		
		if(cnt > ans) {
			ans = cnt;
		}
	}
	
	
	static class Point{
		int r,c;
		Point(int r, int c){
			this.r = r;
			this.c = c;
		}
	}

}