[백준]14502번 연구소(java)

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

14502번: 연구소

DFS + BFS문제이다.

 

 

핵심 

3개의 벽을 반드시 세워야 한다. 처음에는 특정조건에 기둥을 세워야 한다고 생각하였지만, N의 값이 8 이하인 것을 보고

모든 경우의 수를 적용해도 된다. 이후 바이러스를 퍼트린다. 남은 0의 개수를 찾는다.

 

 

 

정답 코드

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

public class Main {
    static int count = 0;
    static int[][] map;
    static boolean[][] visited;
    static int n;
    static int m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        setWall(0);
        System.out.println(count);
    }

    private static void setWall(int wallCount) {
        if (wallCount == 3) {
            int[][] copyMap = new int[n][m];

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

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (copyMap[i][j] == 2) {
                        bfs(copyMap,i, j);
                    }
                }
            }
            findCount(copyMap);
            return;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && map[i][j] == 0) {
                    visited[i][j] = true;
                    map[i][j] = 1;
                    setWall(wallCount + 1);
                    visited[i][j] = false;
                    map[i][j] = 0;
                }
            }
        }
    }


    private static void bfs(int[][] copyMap, int y, int x) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{y, x});

        int[] dy = {1, 0, -1, 0};
        int[] dx = {0, -1, 0, 1};
        while (!q.isEmpty()) {
            int[] move = q.poll();
            for (int i = 0; i < 4; i++) {
                int moveY = move[0] + dy[i];
                int moveX = move[1] + dx[i];
                if (0 > moveY || 0 > moveX || moveY >= n || moveX >= m) {
                    continue;
                }
                if (copyMap[moveY][moveX] == 0 && !visited[moveY][moveX]) {
                    q.offer(new int[]{moveY, moveX});
                    copyMap[moveY][moveX] = 3;
                }
            }
        }
    }

    private static void findCount(int[][] copyMap) {
        int c = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyMap[i][j] == 0) {
                    c++;
                }
            }
        }
        count = Math.max(c, count);
    }
}

해설

기둥을 모든 경우를 구해야 하기 때문에 visited 배열을 사용한다.

모든 경우의 수를 탐색하며 기둥을 세워준다.

이제 바이러스를 퍼트려야 하는데 중요한 점은 기존 map에 퍼트리게 된다면 다시 이전상태로 되돌리기가 어렵다.

따라서 copyMap을 사용하여 바이러스를 퍼트린다. 

이때 퍼진 위치는 3을 지정하였다. 따라서 이미 퍼진 위치는 탐색하지 않는다.

이후 copyMap에 0의 개수를 찾아 최댓값을 구하게 된다.

 

 

배운 점

처음에 map의 값이 copyMap과 동일하게 바뀌어서 계속해서 무엇이 문제인지 고민하며 코드를 주시하였었다.

이유는 처음에 배열을 복사할 때 얕은 복사를 사용하였었다. 따라서 주소를 공유하여 값이 같이 변하게 되었다.

 

얕은 복사(Shallow Copy) : 복사된 배열이나 원본배열이 변경될 때 서로 간의 값이 같이 변경됩니다.

-> int [] a = b;

깊은 복사(Deep Copy) : 복사된 배열이나 원본배열이 변경될 때 서로 간의 값은 바뀌지 않습니다.

-> int [] a = b.clone();

 

오늘도 쉽지만 간과하기 쉬운 사실을 배웠다. 매일 성장하자