백준 14502 <연구소>

이 문제 또한 완전탐색의 가장 기본적인 문제라고 볼 수 있다. 가장 기본적인 틀로는 0이 있는 자리를 3가지만 뽑는 조합으로 구한 다음 DFS 또는 BFS를 통해 바이러스를 퍼트린 다음 빈칸을 세어주는 문제로 간단하게 풀 수 있다 .

 예전에는 다른 방법을 찾아보고 그랬었는데 가장 먼저 이런 문제를 완전탐색으로 접근하고 시간복잡도를 계산한 다음 가능하다면 완전탐색으로 문제를 해결하도록 성장하였다.

 

 이 문제를 완전 탐색으로 푼다면 전체가 0이라고 해도 조합을 계산해본다면 최대크기가 8*8 64이기때문에 3개를 뽑는다고 해도 64C3 이기때문에 41664번이 수행될것이고 완전탐색을 그 후에 한다고 해도 2666496으로 300만이 넘지 않는다. 그러므로 완전탐색으로 접근이 가능한 문제인 것이다.

 

우선적으로 값을 입력할때 바이러스의 위치를 새로운 ArrayList<Point> 에 추가해주고 0이 있는곳은 count를 해서 총 0의 갯수를 알도록 설정했다.

 

이 start함수는 총 3개의 공간에 벽을 세울수 있도록 하는 재귀함수이다 

i가 입력한곳과 같을 때 즉 시작열에서는 b부터 시작하도록 설정했고 그다음열부터는 0부터 검색하게 짜준것이 이 코드의 포인트이다.

 

이전에 작성했던 일차원 배열로 나타내서 조합을 세운것이 아닌 2차원 배열에서의 조합을 구하는 방법이다.

 

이전에 작성했던 코드처럼 나타내려면 

이렇게 a라는 포인트 ArrayList를 만들어 0의 위치를 다 add시켜 저장하고 하는 방법이 있다. 

 

이렇게 0위치를 값을 1로 바꿔주고 다음으로 진행되는 방법으로 구성했다.

빈 칸의 개수는 3개 이상이다. 라는 조건문이 있기에 이렇게 작성이 가능한것이기 때문에 만약 그렇지 않다면 

 

 

이 동그라미 친 부분처럼 처리를 해줘 다음으로 넘어가야 할 것이다.

 

sup의 부분은 벽을 3개를 입력하고 난뒤 실행 시키는 것으로 바이러스 부터 DFS를 실행 시켜주는 함수이다.

 

visit배열을 초기화 시켜주고 모든 바이러스로 부터 퍼트린 후에 max값을 업데이트 시켜주는 것이다.

여기서 DFS를 하면서 다음으로 넘어가게 되면 count를 시켜줘 오염된 공간을 더해 줄 수 있다.

 

이렇게 기본적인 완전탐색 문제에 대해 살펴볼 수 있었다.

 

전체 코드

package practice;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static int visit[][], map[][],div[][]= {{-1,0},{0,1},{1,0},{0,-1}};
	static int N, M,count,sum=0,max=0;
	static ArrayList<Point> whkvy = new ArrayList<Point>();

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		visit = new int[N][M];
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = kb.nextInt();
				if (map[i][j] == 2) {
					whkvy.add(new Point(i,j));
				}
				else if(map[i][j] == 0)
					sum++;
			}
		}
		start(0, 0, 0);
		System.out.println(max);

	}

	public static void start(int k, int a, int b) {
		if (k == 3){
			sup();
            return ;
        }
		for (int i = a; i < N; i++) {
			if (i == a) {
				for (int j = b; j < M; j++) {
					if(map[i][j]==0) {
						map[i][j]=1;
						start(k+1, i, j);
						map[i][j]=0;
					}
				}
			} else {
				for (int j = 0; j < M; j++) {
					if(map[i][j]==0) {
						map[i][j]=1;
						start(k+1, i, j);
						map[i][j]=0;
					}
				}
			}
		}
	}


	public static void sup() {
		count=0;
		visit=new int[N][M];
		for(int i=0;i<whkvy.size();i++) {
			for(int j=0;j<4;j++) {
				scan(whkvy.get(i).x+div[j][0],whkvy.get(i).y+div[j][1]);
			}
		}
		if(max<sum-count-3)
			max=sum-count-3;
	}
	public static void scan(int x1,int y1) {
		if(x1<0||y1<0||x1>=N||y1>=M||visit[x1][y1]==1||map[x1][y1]!=0) {
			return;
		}
		visit[x1][y1]=1;
		count++;
		for(int i=0;i<4;i++) {
			scan(x1+div[i][0],y1+div[i][1]);
		}
	}

}