BJ G5 17141 연구소2

BJ G5 17141 연구소2

 

 

문제링크

www.acmicpc.net/problem/17141

17141번: 연구소 2

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

 

핵심 컨셉

고려사항

 * 이차원 배열을 이용한 사방탐색 문제. 기본적으로는 BFS 기반의 완탐 처리
 * 연구소 상태에서 2로 주어진 공간이 실제 바이러스가 놓인 곳이 아니라 놓을 곳이라는 점에 주의
  -  2의 공간이 K개, 놓은 바이러스 개수가 m개 일 때 kCm을 구한 후 그 상황에서 각 바이러스를 기점으로 완탐
 * 2인데 바이러스가 놓이지 않은 공간은 일반 공백으로 간주해야하므로 실제 바이러스가 놓인 지점을 3으로 마킹하고 처리하자.
 * 깨끗한 영역의 개수를 미리 구해놓고 오염된 영역의 개수가 깨끗한 영역의 개수와 같아지면 성공
  -  성공 했을 때의 bfs 너비를 구하는 문제 

입력사항

 * 연구소의 크기: N(5 ≤ N ≤ 50)
 * 처음에 놓을 바이러서의 개수:  M(1 ≤ M ≤ 10)
 * 연구소의 상태: 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸

출력사항

 * 연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간 출력
 * 모든 빈 칸에 바이러스를 퍼뜨릴 수 없을 경우는 -1 출력

 

동영상 설명

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

youtu.be/7Pelu9H0hK4

 

 

소스보기

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

package bj.gold.l5;

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


public class BJ_G5_17141_연구소2 {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static int N; // 지도 크기
    static int M;// 바이러스 개수

    static int[][] map;
    static List<Point> virusBase; // 바이러스를 놓을 수 있는 위치들 : 지도에서 2인 위치
    static Point[] realVirus;// 실제 바이러스의 위치들

    static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    static int clean; // 초기 오염되지 않은 영역의 개수

    static int Min;
    static int Virus = 3;// 바이러스


    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];

        virusBase = new ArrayList<>();
        clean = N * N;
        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) {
                    virusBase.add(new Point(r, c, 0));
                } else if (map[r][c] == 1) {
                    clean--;
                }
            }
        }
        // 입력 완료.
        realVirus = new Point[M];
        Min = Integer.MAX_VALUE;
        // points에서 virus를 퍼뜨릴 수 있는 경우의 수 찾기
        combi(M, 0);

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

    static void combi(int ti, int si) {
        if (ti == 0) {
            // 그 상황에서 탐색해보기
            // System.out.println(Arrays.toString(viruses));
            pollution();
            return;
        }
        for (int i = si; i < virusBase.size(); i++) {
            realVirus[ti - 1] = virusBase.get(i);
            combi(ti - 1, i + 1);
        }
    }

    static void pollution() {
        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        // 바이러스 놔보기
        for (Point p : realVirus) {
            map[p.r][p.c] = Virus;// 3을 바이러스라고 하자.
            // 각 바이러스 지점에서 BFS 탐색
            q.offer(p);
            visited[p.r][p.c] = true;
        }


        int time = 0;
        int polluted = 0;;
        while (!q.isEmpty()) {
            Point front = q.poll();
            // 최소 값보다 크다면 어차피 의미가 없다.
            if (front.d > Min) {
                break;
            }
            polluted++;
            time = front.d;

            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] == 0 || map[nr][nc] == 2) && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.offer(new Point(nr, nc, front.d + 1));
                }
            }
        }

        if (polluted == clean) {
            Min = Math.min(Min, time);
        }

        // 원상복귀
        for (Point p : realVirus) {
            map[p.r][p.c] = 2;// 3을 바이러스라고 하자.
        }
    }

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

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

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

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


    }

    private static String src = "7 3\r\n" +
                                "2 0 0 0 1 1 0\r\n" +
                                "0 0 1 0 1 2 0\r\n" +
                                "0 1 1 0 1 0 0\r\n" +
                                "0 1 0 0 0 0 0\r\n" +
                                "0 0 0 2 0 1 1\r\n" +
                                "0 1 0 0 0 0 0\r\n" +
                                "2 1 0 0 0 0 2";
}