[JAVA] 백준 14502 연구소

📝 문제

📎 백준 14502 연구소

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


// 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 함
// 0 : 빈칸,  1: 벽, 2: 바이러스
public class Baek_14502 {

    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static int N,M;
    static int[][] virusmap;
    static int maxsafezone = Integer.MIN_VALUE;   // 안전구역의 최대 개수를 위해 최솟값을 저장해둘 변수 설정

    static void countWall(int wallcount) {  // 벽(1)의 개수가 3개가 되면 안전구역을 찾을 함수(bfs)를 불러줄 함수(dfs)
        if(wallcount == 3) {
            countsafezone();
            return; // 종료하고 재귀함수
        }
        for(int i=0; i<N; i++) {
            for (int j = 0; j < M; j++) {
                if(virusmap[i][j] == 0) {
                    virusmap[i][j] = 1;
                    countWall(wallcount+1);
                    virusmap[i][j] = 0;    // 함수가 끝나면 다시 벽을 없애준다.
                }
            }
        }
    }

    static void countsafezone() {
        Queue<int[]> queue = new LinkedList<>();

        for(int i=0; i<N; i++) {
            for (int j = 0; j < M; j++) {
                if( virusmap[i][j] == 2) {      // 바이러스가 있는 곳이라면
                    queue.offer(new int[] {i,j});
                }
            }
        }
        int copyvirusmap[][] = new int[N][M];
        for(int i=0; i<N; i++) {
            copyvirusmap[i] = virusmap[i].clone();      // 배열의 깊은 복사 => 복사 배열이 수정된다해도 원본 배열에 영향을 주지 못함
        }
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            for(int i=0; i<4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];

                if(nx>=0 && ny>=0 && nx<N && ny<M && copyvirusmap[nx][ny] == 0) {
                    queue.offer(new int[] {nx,ny} );
                    copyvirusmap[nx][ny] = 2;
                }
            }
        }
        findsafezone(copyvirusmap);
    }

    static void findsafezone(int[][] copyvirusmap) {
        int safezone = 0;
        for(int i=0; i<N; i++) {
            for (int j = 0; j < M; j++) {
                if(copyvirusmap[i][j] == 0) {
                    safezone ++;
                }
            }
        }
        if(safezone > maxsafezone) {
            maxsafezone = safezone;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        virusmap = new int[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < M; j++) {
                virusmap[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        countWall(0);
        System.out.println(maxsafezone);
    }
}

✅ 문제 접근

제약 조건부터 살펴보자

1. M은 9보다 작은 수
2. 빈 칸의 개수는 3개 이상
3. 벽(1) 은 반드시 3개를 세운다.

코드에서 변수 & 함수 이름이 비슷해 헷갈릴 수 있기 때문에 각자 무엇인지 설명하자면

변수

• virusmap : 원본 배열
• copyvirusmap : 원본 배열을 "깊은복사" 한 복사 배열
• safezone : 바이러스가 퍼져있지 않은 구역의 수
• maxsafezone : safezone 의 최대 개수를 저장하는 변수

함수

• countwall() : 벽(1) 의 개수가 3개가 되면 countsafezone() 를 호출해줄 BFS 함수
• countsafezone() : 원본 배열을 망가뜨리지 않고 바이러스(2)를 퍼진 후 배열을 findsafezone()에 리턴할 DFS 함수
• findsafezone() : countsafezone() 에 받은 copyvirusmap에서 안전구역(0)의 개수를 세어서 maxsafezone 변수에 저장해주는 함수

❓ 앝은 복사 / 깊은 복사

1. 앝은 복사 : 복사한 배열이 원래 배열의 주솟값을 가져온다.

• 단순한 변수 선언을 통한 복사의 형태로, 복사하려는 배열의 주솟값을 가져온다. 그래서 복사한 배열을 수정하게 될 경우, 원래 배열 또한 수정되는 결과를 얻게 된다.
  ex) int[] a = {1,2,3};
  int[] b = a; // 만약 b가 수정되면 a도 수정된다.

2. 깊은 복사 : 복사한 배열이 원래 배열을 그대로 가져온다.

• 원래 배열을 그대로 가져와 새 배열에 덮어쓰기 하는 것
  따라서 복사한 배열을 수정하더라도, 원래 배열이 수정되는 일은 없다.
  ex) int[] a = {1,2,3};
  int[] b = a.clone(); //b가 수정되더라도 a배열에는 영향이 없다.

코드에서 깊은 복사

int copyvirusmap[][] = new int[N][M];
for(int i=0; i<N; i++) {
       copyvirusmap[i] = virusmap[i].clone();      // 배열의 깊은 복사 => 복사 배열이 수정된다해도 원본 배열에 영향을 주지 못함
    }

• virusmap 의 행을 깊은복사로 배열을 복사한다.