[이코테BOJ] 연구소 14502.java

 문제

www.acmicpc.net/problem/14502

14502번: 연구소

- DFS/BFS 문제이다.

- 바이러스가 최소 개수가 될 수 있도록 벽 3개를 반드시 세워야 한다.

- 시간제한이 2초로 꽤나 넉넉한 문제이다.

 

 해설 및 코드

- 시간초과가 날까봐 쉽게 접근하지 못했던 문제이다.

- 시간은 꽤 넉넉하니, 모든 경우의 수를 세면 됐었다.

- 백트레킹으로 벽을 세울때/세우지 않을 때를 나눠서 3개를 세우면 바이러스를 퍼트린다.

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

public class 연구소_14502 {

	private static int N;
	private static int M;
	private static int[][] map;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		map = new int[N][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		
		int cnt = 0;
		
        // 0, 0 부터 dfs 시작
		dfs(0,0,0);

		System.out.println(max);
	}
	static int max = 0;
	static class Node{
		int r;
		int c;
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	private static void dfs(int r, int c, int cnt) {
		// TODO Auto-generated method stub
		int[] dr = { 1, -1, 0, 0 };
		int[] dc = { 0, 0, 1, -1 };

		// cnt는 벽의 개수이다.
		if (cnt == 3) {
			// 벽을 다 세웠으니까 바이러스 퍼트린 후 안전 개수 세기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
                	//바이러스가 시작점이면서 들리지 않았을 때
					if(map[i][j] == 2 && !check[i][j]) {
						
                        //if일 때 이므로 깊은 복사 진행
						int[][] map2 = new int[N][M];

						Queue<Node> q = new LinkedList<>();
						boolean[][] check = new boolean[N][M];
						
						for (int j2 = 0; j2 < N; j2++) {
							for (int k = 0; k < M; k++) {
								map2[j2][k] = map[j2][k];
								if(map2[j2][k] == 2) {

									q.add(new Node(j2,k));
									check[j2][k] = true;
								}
							}
						}

						
						//bfs 시작
						
						while(!q.isEmpty()) {
							Node buf = q.poll();
							for (int d = 0; d < 4; d++) {
								int cr = buf.r + dr[d];
								int cc = buf.c + dc[d];
								
								if(cr<0 || cc<0 || cr>=N || cc>=M || map2[cr][cc] != 0 || check[cr][cc])
									continue;
								
								check[cr][cc] = true;
								map2[cr][cc] = 2;
								q.add(new Node(cr,cc));
							}
						}
						
                        //안전 구역 세기
						int rst =0;
						for (int k = 0; k < N; k++) {
							for (int k2 = 0; k2 < M; k2++) {
								if(map2[k][k2] == 0) {
									rst++;
								}
							}
						}
			
						max = Math.max(max, rst);
					}
				}
			}
			return;
		}

		// 백트레킹
        // (i, j)에 벽을 세울 때와 세우지 않을 때를 모두 체크한다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
					cnt++;
					dfs(i, j, cnt);
					map[i][j] = 0;
					cnt--;
				}
			}
		}

	}
}