BJ G4 17142 연구소3

BJ G4 17142 연구소3

 

 

문제링크

http://www.acmicpc.net/problem/17142

17142번: 연구소 3

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

핵심 컨셉

고려사항

 * 전체 2로 표현되어있는 지점들의 개수를 K개라고 할 때 이중 M개를 순서 없이 활성화 시키므로 kCm의 조합을 찾는 것이 첫번째 임무
  -  따라서 맵을 읽는 과정에서 바이러스 지점들의 목록을 만들어준다.
  -  또한 아직 오염되지 않은 지점 즉 0인 지점도 따로 관리한다.
 * 이제 선택된 m개의 바이러스가 주변으로 전파됨 --> BFS등으로 사방 탐색 시행
 * 최종 목표는 바이러스가 전체로 전파되는 최소 시간(depth)를 출력하는 것
 * 전염이 완료되는 시점을 파악하기 위해 먼저 오염되지 않은 영역들을 카운트 해놓자 - 지도상에서 0인 지점들
 * 활성상태이건 비활성 상태이건 바이러스는 바이러스임의 유의할것 - 비활성화된 지점도 이미 오염된 지점
 * BFS 완탐 과정에서 새롭게 오염되는 영역을 카운트 하나씩 카운트

 

입력사항

 * 연구소의 크기 N(4 ≤ N ≤ 50)
 * 바이러스의 개수 M(1 ≤ M ≤ 10)
 * 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치

출력사항

 * 연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력
 * 불가능한 경우 -1

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/SwzgEGoM7LE

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

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

public class BJ_G4_17142_연구소3 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens = null;

    static int N;
    static int M;

    // 바이러스가 있는 지점들(활성 + 비활성)
    static List<Point> viruses = null;
    // 활성화된 바이러스들
    static Point[] activated = null;

    static int[][] map;
    // 깨끗한 지점들 - 전파의 완료를 파악하기 위한 변수
    static int clean;
    static int Min;

    // 사방 탐색
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));

        tokens = new StringTokenizer(input.readLine(), " ");
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());

        map = new int[N][N];
        activated = new Point[M];
        viruses = new LinkedList<>();

        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(input.readLine(), " ");
            for (int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
                if (map[r][c] == 2) {
                    // 바이러스 지점 저장하기
                    viruses.add(new Point(r, c, 0));
                } else if (map[r][c] == 0) {
                    // 오염되지 않은 지점 카운트 하기
                    clean++;
                }
            }
        }

        Min = Integer.MAX_VALUE;
        // 전체 바이러스 중에서 M개의 활성 바이러스를 고르는 것에서 부터 시작
        combi(M, 0);

        System.out.println(Min == Integer.MAX_VALUE ? -1 : Min);
    }

    static void pollution() {
        boolean[][] visited = new boolean[N][N];
        Queue<Point> q = new LinkedList<>();
        // 활성화된 바이러스 들을 기점으로 BFS 탐색
        for (int i = 0; i < activated.length; i++) {
            q.offer(activated[i]);
            visited[activated[i].r][activated[i].c] = true;
        }

        // 바이러스가 전파되는데 소요되는 시간
        int time = 0;
        // 오염된 지역의 개수
        int polluted = 0;
        while (!q.isEmpty()) {
            Point front = q.poll();
            // 시간은 front의 depth로 변경
            time = front.d;
            // 해당 지점이 공백이었다면 polluted 증가. 비활성화된 바이러스 구간은 오염되지 않음 중의
            if (map[front.r][front.c] == 0) {
                polluted++;
            }
            // 만약 오염지역의 개수가 clean과 동일하면 그만~
            if (polluted == clean) {
                Min = Math.min(time, Min);
                break;
            }
            for (int d = 0; d < dirs.length; d++) {
                int nr = front.r + dirs[d][0];
                int nc = front.c + dirs[d][1];

                if (isIn(nr, nc) && map[nr][nc] != 1 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    Point np = new Point(nr, nc, front.d + 1);
                    q.offer(np);
                }
            }

        }
    }

    static boolean isIn(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < N;
    }

    // 그냥 뻔한 조합 코드
    static void combi(int ti, int si) {
        if (ti == 0) {
            pollution();
            return;
        }

        for (int i = si; i < viruses.size(); i++) {
            activated[ti - 1] = viruses.get(i);
            combi(ti - 1, i + 1);
        }
    }

    static class Point {
        int r, c;
        int d;

        public Point(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }

        @Override
        public String toString() {
            return "[r=" + r + ", c=" + c + ", d=" + d + "]";
        }
    }
}