[Java] 백준 14502번 : 연구소

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

14502번: 연구소

[문제]

[입력]

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

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

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

[출력]

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

[예제 입력]

[풀이 과정]

 벽을 3개를 세운뒤 바이러스가 전부 퍼지고 난 후의 연구소의 안전 영역의 크기를 구하는 문제이다.

 

크게 생각해 볼 점은 다음과 같다.

 

1 ) 3개의 벽을 어떻게 세울것인가?

2 ) 3개의 벽을 세운 후 바이러스는 어떻게 퍼트릴것인가? 

 

 

 

[첫 번째 : 3개의 벽을 어떻게 세울것인가?]

 

 처음 이 문제를 접근 했을 때 3개의 벽을 세우는 기준을 찾으려고했다. 하지만 너무나 복잡했다.. 따라서 완전 탐색을 통해 3개의 벽을 세우는 모든 경우의 수를 구해야 겠다는 생각이 들었다.

 

3개의 벽을 세우는 방법은 이러하다.

 public static void wall (int start ,int depth){
     //start = 시작점 , depth = 세운 벽의 개수 
     //list = 바이러스의 좌표값을 가지고 있다.
     
        if(depth==3){//벽을 3개 세웠다면 너비우선 탐색으로 바이러스를 퍼트린다.
            copyArray(); // 벽3개를 세운 연구실 정보에 대한 배열만든다.
            for (virus v : list) { //바이러스를 퍼트린다.
                Bfs(v.x,v.y);
            }
            safeZone(virus_array); // 안전 영역의 크기를 구한다.
            return;
        }

		//예 : N =4  ,M = 5, N *  M =20
        // i가 0~19까지 (총 20개) 반복문을 돌면서 행과 열의 값을 구한다.
        // i= 13이면  행 = 13/5 =2 이고 열은 13 % 5 = 3이다 
        // 각각의 행과 열을 한번씩 접근하게 된다.

        for (int i = start; i <N * M; i++) {
            int x = i / M;  // 행
            int y = i % M;  // 열

            if (a[x][y] == 0) {
                a[x][y] = 1; //벽을 세운다.
                wall(i + 1, depth + 1); //다음 시작위치와 , 벽의 개수를 넘겨준다.
                a[x][y] = 0; //벽을 다시 없애준다.
            }
        }
    }

 

3개의 벽을 세웠다면 3개의 벽을 세운 연구소 정보(2차원배열) 를 새로 만든 2차원 배열에 복사해준다.  3개의 벽을 세우는 경우가 각각 다르기 때문에 바이러스가 퍼지는 것도  달라지기 때문이다.

 public static void copyArray (){
 		//virus_array = 3개의 벽을 세운 연구소 (2차원 배열) 정보
        virus_array = new int[N][M];
        for(int i = 0 ; i < N; i++){
            for(int j = 0 ;  j <M ;j++){
                virus_array[i][j]=a[i][j];
            }
        }
    }

 

[두 번째 : 3개의 벽을 세운 후 바이러스는 어떻게 퍼트릴것인가? ]

 

바이러스는 상화좌우로 인접한 빈 칸으로 퍼져나간다. 저장한 연구소의 바이러스 좌표들을 가지고 너비 우선 탐색을 하여 바이러스를 퍼트린다.

 

  public static void Bfs(int x, int y){
  
//int [] dot_X = {0,0,1,-1}
//int [] dot_Y = {-1,1,0,0}
//x,y =현재 바이러스 위치

            for(int i = 0 ; i < 4 ; i++){
                int next_X = x+dot_X[i];
                int next_Y = y+dot_Y[i];


                if(next_X < N && next_X >= 0 && next_Y < M && next_Y >=0 ){
                    if(virus_array[next_X][next_Y]==0){
                        virus_array[next_X][next_Y]=2; //바이러스
                        //방문가능한 다음 좌표값을 가지고 너비우선 탐색을 시작한다.
                       Bfs(next_X,next_Y);

                    }
                }
            }

    }

 

너비 우선 탐색을 통해 바이러스를 퍼트리고 난 후의 안전영역의 개수를 구한다.

    public static void safeZone (int [][] virus_array){ //안전한 벽의 개수를 세어주고 최대값을 찾는다.

        int count =0;

        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j  <M ;j++){
                if(virus_array[i][j]==0){
                    count++;
                }

            }
        }

        answer =Math.max(count,answer); //전의 값과 비교하여 최대값으로 갱신한다.
    }

 

[코드]

[결과]