BOJ17142_연구소3

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

문제요약

1. map의 크기 = N , 활성상태로 만들 수 있는 바이러스 수 = M , 비활성 상태 바이러스 = 2 , 빈 공간 = 0 , 벽 = 1

2. 활성상태로 만든 바이러스는 동시에 상하좌우 빈공간 또는 비활성 상태 바이러스로 퍼진다

3. 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자

문제issue

1. 모든 빈 칸에 바이러스가 있게 되는 최소 시간이란 비활성 상태의 바이러스도 포함한다.

-> (1) 입력 받을 때 모든 빈칸을 카운트 해준다 zero_cnt

    (2) 활성상태의 바이러스에서 빈공간(비활성 바이러스는 제외)으로 퍼진 개수를 카운트 해준다 zero_check

    (3) 위 두개의 카운트를 비교했을 때 zero_cnt <= zero_check 라면 모든 빈공간이 바이러스가 된 순간이다.

    (4) min 값을 갱신 해줄 때도 모든 빈공간이 바이러스가 된 상태일때만 갱신해준다.

해결흐름

1. 입력 받을 때 0의 개수를 카운트해주고 2인 곳의 위치를 list에 저장해준다.

2. list에 있는 것 중 M개의 조합을 구해준다.

3. 조합마다 bfs()를 수행하여 경과된 시간을 구해준뒤 min값을 갱신해준다.

소스코드

2019.05

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    
    static class pair{
        int r;
        int c;
        public pair(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
 
    private static int N;
    private static int M;
    private static int[][] map;
    private static int[][] map_clone;
    private static boolean[][] visited;
    private static int zero_cnt;
    private static ArrayList<pair> list;
    private static ArrayList<pair> temp;
    private static LinkedList<pair> q;
    private static int time;
    private static int[] dr = {-1,0,1,0};
    private static int[] dc = {0,1,0,-1};
    private static int min;
    private static int zero_check;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        list = new ArrayList<pair>();
        temp = new ArrayList<pair>();
        zero_cnt = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                int number = Integer.parseInt(st.nextToken());
                map[i][j] = number;
                if(number == 0) {
                    zero_cnt++;
                }
                if(number == 2) {
                    list.add(new pair(i, j));
                }
            }
        }
        min = Integer.MAX_VALUE;
        comb(0, 0);
        if(min == Integer.MAX_VALUE) {
            System.out.println(-1);
        }
        else {
            System.out.println(min);
        }
        
    } // end of main
 
    private static void comb(int len, int k) {
        if(len == M) {
            bfs();
            if(zero_cnt <= zero_check && min > time) {
                min = time;
            }
            return;
        }
        for (int i = k; i < list.size(); i++) {
            temp.add(new pair(list.get(i).r, list.get(i).c));
            comb(len+1, i+1);
            temp.remove(len);
        }
    }
 
    private static void bfs() {
        // map에서 퍼지는 변화를 확인하기 위한 map_clone
        map_clone = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map_clone[i][j] = map[i][j];
            }
        }
        zero_check = 0;
        time = 0;
        q = new LinkedList<pair>();
        visited = new boolean[N][N];
        
        for (int i = 0; i < temp.size(); i++) {
            pair p = temp.get(i);
            int r = p.r;
            int c = p.c;
            q.add(new pair(r,c));
            visited[r][c] = true;
        }
        int insert_number = 11;
        while(!q.isEmpty()) {
            int q_size = q.size();
            if(zero_check >= zero_cnt) {
                return;
            }
            insert_number += 11;
            for (int i = 0; i < q_size; i++) {
                pair p = q.poll();
                int r = p.r;
                int c = p.c;
                for (int j = 0; j < 4; j++) {
                    int nr = r + dr[j];
                    int nc = c + dc[j];
                    if(nr>=0 && nr<N && nc>=0 && nc<N
                            && !visited[nr][nc] && (map[nr][nc] == 0 || map[nr][nc] == 2)) {
                        q.add(new pair(nr,nc));
                        visited[nr][nc] = true;
                        map_clone[nr][nc] = insert_number;
                        // 퍼진개수 체크
                        if(map[nr][nc] == 0) {
                            zero_check++;
                        }
                    }
                }
            }
            time++;
        }
    }
} // end of class

2019.09

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static class pair {
        int r;
        int c;
 
        public pair(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
 
    private static ArrayList<pair> list;
    private static int zero_total;
    private static int N;
    private static int M;
    private static int[][] map;
    private static boolean[][] visited;
    private static pair[] C_arr;
    private static boolean[] list_visited;
    private static int min_time;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        visited = new boolean[N][N];
        list = new ArrayList<pair>();
        zero_total = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 0; j < N; j++) {
                int number = Integer.parseInt(st.nextToken());
                map[i][j] = number;
                if (number == 0) {
                    zero_total++; // 전체 빈곳의 개수
                } else if (number == 2) {
                    list.add(new pair(i, j));
                }
            }
        }
        list_visited = new boolean[list.size()];
        C_arr = new pair[M];
        min_time = Integer.MAX_VALUE;
        nCm(0, 0);
        if (min_time == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(min_time);
    } // end of main
 
    private static void nCm(int len, int t) {
        if (len == M) {
//            System.out.println("======================");
//            for (int i = 0; i < C_arr.length; i++) {
//                System.out.println("r : " + C_arr[i].r + " c : " + C_arr[i].c);
//            }
            bfs();
            if (zero_total - zero_cnt == 0) {
//                System.out.println("time : " + time);
                if (min_time > time)
                    min_time = time;
            }
            return;
        }
        for (int i = t; i < list.size(); i++) {
            if (!list_visited[i]) {
                list_visited[i] = true;
                C_arr[len] = list.get(i);
                nCm(len + 1, i + 1);
                list_visited[i] = false;
            }
        }
    }
 
    private static int[] dr = { -1, 0, 1, 0 };
    private static int[] dc = { 0, 1, 0, -1 };
    private static int time;
    private static int zero_cnt;
 
    private static void bfs() {
        visited = new boolean[N][N];
        Queue<pair> q = new LinkedList<pair>();
        for (int i = 0; i < C_arr.length; i++) {
            int r = C_arr[i].r;
            int c = C_arr[i].c;
            q.add(new pair(r, c));
            visited[r][c] = true;
        }
        time = -1;
        zero_cnt = 0;
        while (!q.isEmpty()) {
            time++;
            if (min_time < time) return; // 더이상 볼필요 없음
            if (zero_total - zero_cnt == 0) return; // 0인곳 다 채웠으면 끝
            int q_size = q.size();
            for (int i = 0; i < q_size; i++) {
                pair p = q.poll();
                int r = p.r;
                int c = p.c;
//                System.out.println("time : " + time + " r : " + r + " c : " + c);
                for (int j = 0; j < 4; j++) {
                    int nr = r + dr[j];
                    int nc = c + dc[j];
                    if (nr >= 0 && nr < N && nc >= 0 && nc < N && !visited[nr][nc] && map[nr][nc] != 1) {
                        if (map[nr][nc] == 0) {
                            zero_cnt++; // 채운곳이 0이면 카운트
                        }
                        visited[nr][nc] = true;
                        q.add(new pair(nr, nc));
                    }
                }
            }
        }
    }
} // end of class

달라진 점

1. 조합과 0의 개수를 카운트하는 방법은 완전 똑같지만 bfs()안에서 가지치기를 해줘서 시작을 조금 절약했다.