[백준 14502]연구소 - 자바

 

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

14502번: 연구소

 

1. 풀이

---

처음엔 dfs와 bfs로만 사용하면 풀릴 줄 알고, 조금 헤맸습니다..

 

완전 탐색을 사용하여 벽을 세우면서 바이러스를 반복적으로 살포(?)하여 안전영역의 최대값을 찾으면 되는 문제였습니다.

 

(1) 완전 탐색을 사용하여 0마다의 벽을 세웁니다.

(2) 추가한 벽의 개수가 3개가 되면 바이러스를 살포(?)하여 안전영역의 개수를 세주고 최대값인지를 체크합니다.

 

 

2. 코드

---

import java.util.*;

public class Main {
	
	static int N;
	static int M;
	static int[] dy = {0,0,-1,1};
	static int[] dx = {-1,1,0,0};
	static int graph[][] = new int[8][8]; // 그래프
	// 벽을 세우고 바이러스 살포용 실험하는 저장
	static int graph_temp[][] = new int[8][8]; 
	static int result = 0;
	
	// dfs
	static void dfs(int a, int b) {
		graph_temp[a][b] = 2; // 방문 체크
		for(int i = 0; i < 4; i++) { // 좌우아래위를 전부 다 훑으면서 dfs진행
			if(a + dy[i] < 0 || a + dy[i] >= N || b + dx[i] < 0 || b + dx[i] >= M) 
				continue;
			if(graph_temp[a+dy[i]][b+dx[i]] == 0) {
				dfs(a+dy[i], b+dx[i]);
			}
		}
	}
	
	static void spreadVirus() {
		
		graphCopy(graph, graph_temp);
		
		// dfs를 사용하여 바이러스 살포
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(graph_temp[i][j] == 2) {
					dfs(i,j);
				}
			}
		}
		
		// 안전영역 카운트
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(graph_temp[i][j] == 0)
					cnt+=1;
			}
		}
		
		// 최대값 검사
		if(cnt > result)
			result = cnt;
	}
	
	static void makeWall(int count) {
		if(count == 3) {
			spreadVirus();
			return;
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(graph[i][j] == 0) {
					graph[i][j] = 1;
					makeWall(count+1);
					graph[i][j] = 0;
				}
			}
		}
	}
	
	// 그래프 복사
	static void graphCopy(int[][] graph, int[][]graph_temp) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				graph_temp[i][j] = graph[i][j];
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		
		N = sc.nextInt(); // 세로 크기
		M = sc.nextInt(); // 가로 크기
		
		// 입력 받기
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				graph[i][j] = sc.nextInt();
			}
		}
		
		// 루프 돌면서 벽 세우기 ( 완전 탐색 )
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(graph[i][j] == 0) {
					graph[i][j] = 1;
					makeWall(1);
					graph[i][j] = 0;
				}
			}
		}
		
		System.out.println(result);
		
		sc.close();
		return;
	}
}