[14502] 연구소

14502번 연구소

문제는 위와 같이 2에서 바이러스가 상하좌우로 점점 퍼질 때 벽 3개를 설치해 안전한 영역을 최대한 크게 만드는 것이다.

여기서 입력으로 주어지는 단위가 아래과 같다.

최대 8X8 사이즈 이기 때문에 3개의 벽을 설치할 수 있는 모든 경우에 대해서 따져도 될것 같다.

---

[ 풀이 ]

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

public class Main {

	public static Scanner sc=new Scanner(System.in);
	public static int N=sc.nextInt();
	public static int M=sc.nextInt();
	public static int ii=0, jj=0, kk=0, hh=0, pp=0, qq=0,count=0, Max=0, midas=0;
	public static int[][] lab=new int[N][M];
	public static boolean[][] virus=new boolean[10][10];
	public static boolean[][] visit=new boolean[10][10];
	public static Queue<Integer> quer=new LinkedList<Integer>();
	public static Queue<Integer> quec=new LinkedList<Integer>();

	public static void BFS(int a, int b) {

		visit[a][b]=true;
		quer.add(a); quec.add(b);
		int coi=0;

		while(!quer.isEmpty()&&!quec.isEmpty()) {
			int rr=quer.poll(); int cc=quec.poll();
				if(rr-1>=0&&lab[rr-1][cc]==0&&visit[rr-1][cc]==false) 
                    {quer.add(rr-1);quec.add(cc);visit[rr-1][cc]=true;coi++;}
				if(cc-1>=0&&lab[rr][cc-1]==0&&visit[rr][cc-1]==false) 
                    {quer.add(rr);quec.add(cc-1);visit[rr][cc-1]=true;coi++;}
				if(rr+1<N&&lab[rr+1][cc]==0&&visit[rr+1][cc]==false) 
                    {quer.add(rr+1);quec.add(cc);visit[rr+1][cc]=true;coi++;}
				if(cc+1<M&&lab[rr][cc+1]==0&&visit[rr][cc+1]==false) 
                    {quer.add(rr);quec.add(cc+1);visit[rr][cc+1]=true;coi++;}
				
		}

		midas+=coi;

	}

	public static void lim(int x1, int y1, int x2, int y2, int x3, int y3) {
		lab[x1][y1]=1;lab[x2][y2]=1;lab[x3][y3]=1;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(virus[i][j]==true)
					BFS(i, j);
				
			}
        }

		if(Max<=count-midas) Max=count-midas;

		lab[x1][y1]=0;lab[x2][y2]=0;lab[x3][y3]=0;
		midas=0;
		visit=new boolean[10][10];
	}

	public static void main(String[] args) {
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				lab[i][j]=sc.nextInt();
				if(lab[i][j]==0) { count++;}
				else if(lab[i][j]==2) {
					virus[i][j]=true;
				}
			}
		}

		count-=3;
        //벽 3개를 세우는 과정... 
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(lab[i][j]==0) {
					ii=i; jj=j;
					for(int k=0; k<N; k++) {
						for(int h=0; h<M; h++) {
							if(!(k==i&&j==h)&&lab[k][h]==0) {
								kk=k; hh=h;
								for(int p=0; p<N; p++) {
									for(int q=0; q<M; q++) {
										if(!(p==i&&j==q)&&!(p==k&&q==h)&&lab[p][q]==0) {
											pp=p; qq=q;
											lim(ii, jj, kk, hh,pp,qq); //안전영역 구하기.
										}
									}
								}
							}
						}
					}
				}
			}
		}
		
		System.out.println(Max);
	}

}

이렇게 보니 정말 긴 코드이다.. 그리고 과거의 나..

어떻게 이런 생각을 했는지 2년전의 나만 알고 있을것 같다..

본론으로 돌아가서 여기서 중요한 점은 다음과 같다.

1.3개의 벽을 세우고 부수고를 반복해 기존 이차원배열을 재활용한다.
2.바이러스 확산을 BFS로 구하고 방문하지 않은 영역중 벽이 아닌 것들은 안전영역으로 하고 넓이를 구한다.

이 두 가지만 반복하였다.

다만… 만약 배열의 크기가 커지면 이 문제를 풀 수 없을 듯하다.
먼저 벽 3개를 세우기 위해 벽을 세울 수 있는 공간을 잡는 과정에서 6중 for문을 이용하기 때문..!

차라리 바이러스를 가둘 수 있도록 벽을 세우는 방식을 좀더 고안하면, 더 효율적인 코드가 나올 것 같다.