[백준 14502] 연구소

이 문제는 벽 3개를 추가한 후 바이러스가 퍼졌을 때의 안전구역의 최대값을 구하는 문제입니다. 저는 재귀함수와 bfs를 이용했습니다. 

제 규칙은 아래와 같습니다.

1. 재귀함수를 이용해 벽 3개 구하기
2. 초기 배열을 cloneMap에 복사하고 구한 3개의 벽도 추가
3. bfs를 수행하며 바이러스를 퍼트린 후 안전영역 개수 구하기

위의 규칙을 토대로, 먼저 N, M, map 세개를 입력받고 나중에 안전구역 영역을 셀 때 또 이중반복문을 수행하지 않기 위해 안전구역갯수(safeAreaCount)를 저장했습니다. 그리고 N*M 만큼 for문을 반복해 이중for문을 피했습니다. 일단 벽 하나를 세운 뒤 recursive 함수를 호출해 벽 2개를 더 세우고 안전구역 영역을 구합니다.

private static void recursive (int num, int count) {
    // 벽 세개 세웠으면 바이러스 퍼트리기
    if (count == 3) {
        copyMap();
        bfs();
    } else {
        for (int i = num + 1; i < N*M; i++) {
            int row = i / M;
            int col = i % M;
            if (map[row][col] == 0) {
                wall.add(row + " " + col);
                recursive(i, count + 1);
            }
        }
    }
    int index = wall.indexOf(num / M + " " + num % M);
    wall.remove(index);
}

recursive함수 내에서는 벽 두개를 추가로 구한 뒤 count 가 3이면 copyMap() 과 bfs()를 수행합니다. 그 후 추가했던 벽을 제거했습니다.

private static void copyMap () {
    queue.clear();
    cloneMap = new int[N][M];

    // 배열 복사
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (cloneMap[i][j] != 1) cloneMap[i][j] = map[i][j];
            if (map[i][j] == 2) queue.offer(new Pos(i, j));
        }
    }

    // 3개 벽 추가
    for (int i = 0; i < 3; i++) {
        String[] str = wall.get(i).split(" ");
        cloneMap[Integer.parseInt(str[0])][Integer.parseInt(str[1])] = 1;
    }
}

copyMap() 에서는 처음 입력받았던 이차원 배열 map을 cloneMap에 복사하고 초기 바이러스를 queue에 담습니다. 그리고 추가했던 벽 3개를 cloneMap 에도 추가해줍니다.

private static void bfs () {
    int result = safeAreaCount - 3;

    // 바이러스 퍼트리기
    while(!queue.isEmpty()) {
        int length = queue.size();
        for (int i = 0; i < length; i++) {
            Pos p = queue.poll();
            for (int j = 0; j < 4; j++) {
                int sx = p.x + dx[j];
                int sy = p.y + dy[j];

                if (sx >= 0 && sx < N && sy >= 0&& sy < M && cloneMap[sx][sy] == 0) {
                    cloneMap[sx][sy] = 2;
                    result--;
                    queue.add(new Pos(sx, sy));
                }
            }
        }
    }
    MAX = Math.max(MAX, result);
}

bfs 에서는 먼저 result 변수에 초기 안전구역 영역의 개수에서 새로 설치한 3개의 벽을 뺀 정수를 넣습니다. 그 후 큐에 바이러스 인덱스를 넣어 while문을 돌며 그 주변으로 바이러스를 퍼트립니다. 바이러스를 퍼트릴 자리를 다시 큐에 넣고, result를 하나 감소시켜 안전구역 영역의 개수를 업데이트 해줍니다. 이런식으로 안전구역 영역의 개수를 구한 뒤 MAX값을 갱신해줍니다.

아래의 소스는 전체 코드입니다.