[백준 14502] - 연구소 자바(JAVA)

 

 

문제

---

출처 - https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

 

 

 

 

문제 풀이

---

• N제한이 8이라는 매우 작은 수 
• 3개의 벽을 세우는 모든 경우의 수를 만드는 DFS
• 벽을 만들고 바이러스를 퍼트리는 과정의 BFS -> 인접한 다른 정점으로 갈때 가중치가 1 

 

*주의!! = 원본 배열을 바꾸면 안되기 때문에 복사된 배열을 사용해야 하는데  a = b 와 같은 대입연산자를 사용하면 얕은 복사가 생겨 원본 배열 값에 영향을 미치기 때문에 깊은복사를 해야한다.

 

 

문제를에 벽의개수는 3개이고 3개를 모두 사용해야 한다는 조건이 있다.

 

1. 연구소 모든 칸에 벽을 세우려면 빈칸인지 확인을 하고 벽을 세워야 하기 때문에 dfs 방식으로 해결 할 수 있다.

 

2. 바이러스는 상하좌우 인접한 방향으로 퍼지고 각 1*1정사각형으로 나누어져 있어 가중치가 1이기 떄문에 BFS를 사용하여 바이러스를 퍼트릴 수 있다.

 

3. 바이러스를 퍼트려 얻을 수 있는 안전 영역의 최대 크기값을 계속 구한다.

 

4. 안전 영역의 최대 크기를 출력한다.

 

아래 코드 주석에 설명을 보면 쉽게 이해가 갈 것이다.

 

 

 

 

소스코드

---

import java.io.*;
import java.util.*;

public class Main {

    static final int dx[] = {0,0,1,-1};  //상하좌우 방향 설정
    static final int dy[] = {1,-1,0,0};  //상화좌우 방향 설정
    static int originalMap[][];
    static int n,m;
    static int maxSafeZone = Integer.MIN_VALUE; //최대값을 찾기 위한 최소값 설정

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        originalMap = new int[n][m];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++) {
                originalMap[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0);

        System.out.println(maxSafeZone);
    }

    static void dfs(int wallCnt) {
        //벽이 3개가 설치 된 경우 bfs 탐색 시작
        if(wallCnt == 3) {
            bfs();
            return;
        }

        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(originalMap[i][j] == 0) {
                    originalMap[i][j] = 1;
                    dfs(wallCnt+1);
                    originalMap[i][j] = 0;
                }
            }
        }
    }

    static void bfs() {
        Queue<Node> q = new LinkedList<>();

        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(originalMap[i][j] == 2) {
                    q.add(new Node(i,j));
                }
            }
        }

        //원본 연구소를 바꾸지 않기 위한 카피맵 사용
        int copyMap[][] = new int[n][m];

        for (int i = 0; i < n; i++) {
            copyMap[i] = originalMap[i].clone();
        }

        //BFS 탐색 시작
        while(!q.isEmpty()) {
            Node now = q.poll();
            int x = now.x; // 현재 값
            int y = now.y; //

            for(int k=0; k<4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                //연구소 범위 밖이 아니고 빈칸일 경우에만 바이러스를 퍼트린다.
                if(0<=nx && nx<n && 0<=ny && ny<m) {
                    if(copyMap[nx][ny] == 0) {
                        q.add(new Node(nx,ny));
                        copyMap[nx][ny] = 2;
                    }
                }
            }
        }

        //SafeZone 확인
        funcSafeZone(copyMap);
    }

    private static void funcSafeZone(int[][] copyMap) {
        int safeZone =0;
        for(int i=0; i<n ; i++) {
            for(int j=0; j<m; j++) {
                if(copyMap[i][j] == 0) {
                    safeZone++;
                }
            }
        }
        if (maxSafeZone < safeZone) {
            maxSafeZone = safeZone;
        }
    }

    //Queue에 좌표값 x,y를 넣기 위함.
    static class Node {
        int x;
        int y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}