백준)Q.14502_연구소(BFS,DFS(재귀함수))

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

14502번: 연구소

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

 

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0

0 0 1 0 1 2 0

0 1 1 0 1 0 0

0 1 0 0 0 0 0

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

 

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0

1 0 1 0 1 2 0

0 1 1 0 1 0 0

0 1 0 0 0 1 0

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

 

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2

1 0 1 0 1 2 2

0 1 1 0 1 2 2

0 1 0 0 0 1 2

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

 

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

 

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

 

예제 입력 1

7 7

2 0 0 0 1 1 0

0 0 1 0 1 2 0

0 1 1 0 1 0 0

0 1 0 0 0 0 0

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

 

예제 출력 1

27

 

예제 입력 2 

4 6

0 0 0 0 0 0

1 0 0 0 0 2

1 1 1 0 0 2

0 0 0 0 0 2

 

예제 출력 2

9

 

예제 입력 3

8 8

2 0 0 0 0 0 0 2

2 0 0 0 0 0 0 2

2 0 0 0 0 0 0 2

2 0 0 0 0 0 0 2

2 0 0 0 0 0 0 2

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

예제 출력 3

3

 

< 나의 풀이 >

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class test3333 {
 
// 알고리즘
// 1. 막고 자시고 간에 3개의 벽을 세울 수 있는 모든 경우의 배열을 보기// 2. 바이러스를 퍼뜨려서 0의 갯수를 구하기// 3. 1,2를 반복하며 이전 안전구역의 최대값(0의 갯수의 최대값)을 비교,저장하기.
 
// Details// main에서 반복문을 돌려 첫번째 벽을 세울 좌표를 지정 후 첫번째 벽을 세움. // -> 이 좌표의 값은 1이나 2가 아니여야 하며 (0,0)부터 시작하여 마지막 좌표까지 순서대로 지정된다.// 두개의 벽을 세우는 메소드에서 main에서 지정해준 기준 좌표외에 추가로 더 세울 수 있는 모든 두개의 
// 구역을 살필 수 있도록 반복문을 구현한다.(재귀함수 이용)// 두개의 벽을 세우는 메소드는 기준좌표(첫번째 벽)외에 세울수 있는 모든 두개의 벽을 세워 본 후 종료된다.// main메소드에서는 그 다음 첫 번째 벽을 세울 좌표를 지정하고 다시 두개의 벽 메소드를 실행한다.// (이 과정을 마지막 좌표까지 반복한다.) 
// 두개의 벽을 세우는 메소드에는 벽이 모두 건설 됐을때 바이러스를 퍼트려 본 후, 0의 갯수를 구한다.// (바이러스를 퍼트리는 메소드, 0의 갯수를 구하는 메소드 필요) // 0의 갯수를 임시 변수에 저장 후 그다음 반복문이 완료됐을 때의 0의 갯수와 비교하여 계속해서 최대값만을 
// 저장해 나간다. 
 
// 필요한 메소드// 1. 배열을 복사하는 메소드// 2. 두개의 벽을 세우는 메소드// 3. 바이러스를 퍼뜨리는 메소드 // 4. 0의 갯수를 구하는 메소드 
 
     static int[][] tmpArr;
     static int[][] arr;
     static int maxOfSafetyZone, row, column;
     static int[] dx = { 0, 0, -1, 1 };
     static int[] dy = { -1, 1, 0, 0 };
 
     public static void main(String[] args) throws IOException {
 
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           Queue Q = new LinkedList();
 
          //////////////////////////////////////////////입력받기
 
           String[] input = br.readLine().split(" ");
           row = Integer.parseInt(input[0]); // Row
           column = Integer.parseInt(input[1]); // Column
           arr = new int[row][column]; // Original array
 
           for (int i = 0; i < row; i++) {
                String[] line = br.readLine().split(" ");
                for (int j = 0; j < column; j++) {
                     arr[i][j] = Integer.parseInt(line[j]);
                }
           }
 
 //////////////////////////////////////////////입력끝
 
           for (int i = 0; i < row; i++) {
                for (int j = 0; j < column; j++) {
                     if (arr[i][j] == 0) {
                           // 1) 첫번째 벽을 세울 수 있으면(원소가 0이면) 배열을 복사
                           tmpArr = new int[row][column];
                           CopyArray(arr, tmpArr);
                           // 2) 벽 세우기 & 벽 갯수++;
                           tmpArr[i][j] = 1;
                           // 3) tmpArr[i][j]외에 세울 수 있는 두개의 벽을 세우기
                           // (BuildWall메소드 안에서 바이러스를 퍼뜨리고, 0의 갯수를 세는 과정 포함)
                           BuildWall(1);
                           // 4) 완료되면 초기화 시켜주기
                           tmpArr[i][j] = 0;
                     }
                }
           }
           System.out.println(maxOfSafetyZone);
     } // end of main
 
 // 배열 복사 메소드 
     static void CopyArray(int[][] org, int[][] copy) {
           for (int i = 0; i < org.length; i++) {
                for (int j = 0; j < org[i].length; j++) {
                     copy[i][j] = org[i][j];
                }
           }
     }
 // 두개의 벽을 세우는 메소드 
     static void BuildWall(int walls) {
           // 벽 세개가 완료되면, 바이러스를 퍼뜨린다.
           if (walls == 3) {
                SpreadVirus(tmpArr);
                return;
           }
 
           for (int i = 0; i < tmpArr.length; i++) {
                for (int j = 0; j < tmpArr[i].length; j++) {
                     if (tmpArr[i][j] == 0) {
                           tmpArr[i][j] = 1;
                           BuildWall(walls + 1);
                           // 완료되면 초기화 시켜주기
                           tmpArr[i][j] = 0;
                     }
                }
           }
     }
 // 바이러스를 퍼트리는 메소드 
     static void SpreadVirus(int[][] arrs) {
           Queue<Node> Q = new LinkedList<>();
           Node current = new Node(0, 0); // current 초기화
           int[][] virused = new int[row][column];
           CopyArray(tmpArr, virused);
 
           // 바이러스가 있는 곳을 Q에 집어 넣는다.
           for (int i = 0; i < virused.length; i++) {
                for (int j = 0; j < virused[i].length; j++) {
                     if (virused[i][j] == 2) {
                           Q.add(new Node(i, j));
                     }
                }
           }
 
           while (!Q.isEmpty()) {
                current = Q.poll();
                for (int k = 0; k < 4; k++) {
                     int nextX = current.x + dx[k];
                     int nextY = current.y + dy[k];
                     if (nextX < 0 || nextY < 0 || nextX >= row || nextY >= column)
                           continue;
 
                     // 바이러스가 있는 좌표의 사방을 비교하여 0이면 2로 변경 후
                     // 2로 변경된 좌표를 Queue에 넣는다.
 
                     if (virused[nextX][nextY] == 0) {
                           virused[nextX][nextY] = 2;
                           Q.add(new Node(nextX, nextY));
                     }
                }
 
                // Q가 비어있으면(바이러스를 모두 퍼뜨렸으면) 0의 갯수를 구하는 메소드 실행.
                if (Q.isEmpty()) {
                     CountingOfSafetyZone(virused);
                     return;
                }
           } // end of while
     }
 // 안전구역(0인구역)을 세는 메소드 
     static void CountingOfSafetyZone(int[][] arrs) {
           int count_0 = 0;
           for (int i = 0; i < arrs.length; i++) {
                for (int j = 0; j < arrs[i].length; j++) {
                     if (arrs[i][j] == 0)
                           count_0++;
                }
           }
           maxOfSafetyZone = maxOfSafetyZone < count_0 ? count_0 : maxOfSafetyZone;
     }
 
 // 노드클래스
     static class Node {
           int x, y;
           public Node(int x, int y) {
                this.x = x;
                this.y = y;
           }
     }
}