[Java] 백준 14502 : 연구소

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

1.

한 2.5시간 정도 소요되었던 것 같다.

 

처음 문제를 보았을 때, 지금까지 풀었던 그래프 문제 알고리즘을 모두 적용하면 풀 수 있을 것이라 생각해서 코드를 써내려 갔다. 근데 코드를 써내려 가면서도 이중 for 문이 너무 많이 나와 비효율적이지 않을까 생각했지만, 시간제한이 2초이므로 문제없다고 판단했다.

(사실 코드 써 내려가면서 갸우뚱만 3번 정도 한 듯..)

 

근데 답이 출력되지 않아 고민해보니 벽을 세우는 알고리즘을 잘못 선택했다는 것을 알아챘다. 조합 알고리즘을 잘못 작성하였다. 이 부분은 이전에 풀었던 조합 문제를 떠올려 적용하려고 했지만, 2차원 배열의 조합 구하는 것은 처음 접하여 풀이를 참고하였다.

 

 

2.

문제의 메커니즘은 다음과 같다.

 

1. 벽을 세울 수 있는 조합을 구하기

2. 바이러스가 퍼질 임시 연구소 tempData에 원래 연구소 복사

3. 모든 위치를 방문하며 바이러스가 있는 곳을 queue에 넣고 방문 표시. queue가 empty가 아닐 때까지 다음을 반복

   3.1 다음 방문할 $nx, ny$ 구하기

   3.2 그것이 조건에 부합하면 queue에 넣고 방문 표시. 바이러스에 퍼졌으므로 2로 변경

4. 배열 전체를 순회하며 감염되지 않은 위치를 카운팅

5. 카운트한 수 중에서 최댓값을 출력

 

 

핵심 알고리즘은 벽을 세우는 조합 (DFS), 바이러스 감염시키는 것 (BFS) 이다.

2차원 배열의 원소의 조합을 구하는 방법이 생소한데, 보통은 2차원 배열을 탐색할 때 중첩 for문을 사용하여 탐색하지만, for문을 하나만 사용해서 탐색하는 것이 가능하다.

 

3.

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

public class Main {
    static int n, m, answer;
    static int[][] data;
    static Queue<Pos> build = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        data = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                data[i][j] = sc.nextInt();
            }
        }

        answer = Integer.MIN_VALUE;
        wall(0, 0);

        System.out.println(answer);
        sc.close();
    }

    static void wall(int start, int depth) {
        if (depth == 3) {
            answer = Math.max(answer, bfs());
            return;
        }

        for (int i = start; i < n * m; i++) {
            int x = i / m;
            int y = i % m;

            if (data[x][y] == 0) {
                data[x][y] = 1;
                wall(i + 1, depth + 1);
                data[x][y] = 0;
            }
        }

    }

    static int bfs() {
        Queue<Pos> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        int[] dx = { -1, 1, 0, 0 };
        int[] dy = { 0, 0, -1, 1 };

        int[][] tempData = new int[data.length][data[0].length];

        for (int i = 0; i < tempData.length; i++) {
            System.arraycopy(data[i], 0, tempData[i], 0, data[0].length);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tempData[i][j] == 2) {
                    q.offer(new Pos(i, j));
                    visited[i][j] = true;

                    while (!q.isEmpty()) {
                        Pos temp = q.poll();

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

                            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                                if (tempData[nx][ny] == 0 && !visited[nx][ny]) {
                                    visited[nx][ny] = true;
                                    tempData[nx][ny] = 2;
                                    q.offer(new Pos(nx, ny));
                                }
                            }
                        }
                    }
                }
            }
        }

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tempData[i][j] == 0) {
                    cnt++;
                }
            }
        }

        return cnt;
    }
}

class Pos {
    int x, y;

    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

 

4.

배열을 복사할 때 단순히 int[] copyArr = copy; 라고 하면 안 된다. 이는 얕은 복사로 copyArr 에 주소 값이 저장되므로 이를 수정하면 원본 배열에 영향을 끼친다.

영향을 끼치지 않도록 하려면 깊은 복사를 해야 하는데, 배열 전체를 순회하며 일일이 복사하여야 한다.

 

2차원 배열에서도 동일하게 하지만, 중첩 배열을 사용하지 않으려면 System.arraycopy() 메소드를 이용하면 된다.

 

 

[참고] https://bcp0109.tistory.com/25

[참고] https://coding-factory.tistory.com/548