[BOJ] 17141. 연구소 2

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

접근 방법

전형적인 부르트 포스 방식으로

바이러스가 있을 수도 있는 장소를 기억을 해놓는 배열을 생성한다.

static ArrayList<Point> canVirus = new ArrayList<>();

map[i][k] = Integer.parseInt(st.nextToken());
                if(map[i][k] == 2){
                    canVirus.add(new Point(i,k));
                    map[i][k] = 0;
                }

그런 후 이 바이러스가 들어 있는 곳에서 문제에서 제시한 M개를 뽑으면 된다.

( 즉 , 바이러스Cm ← 조합의 의미 ) =⇒ 바이러스가 있을 수 있는 곳 중 M개를 순서 상관 없이 뽑기.

static void permutation(int n, int r, int peek, boolean[] virus){
        if(r == 0){
            setVirus = new ArrayList<>();
            for(int i=0; i<canVirus.size(); i++) {
                if(virus[i]){
                    setVirus.add(new Point(canVirus.get(i).x, canVirus.get(i).y));
                    map[canVirus.get(i).x][canVirus.get(i).y] = 2;
                }
            }
            spreadVirus();
            ans = Math.min(getTime(),ans);

            for(int i=0; i<canVirus.size(); i++) {
                map[canVirus.get(i).x][canVirus.get(i).y] = 0;
            }
            return;
        }
        for(int i=peek; i<n; i++){
            virus[i] = true;
            permutation(canVirus.size(), r-1, i+1, virus);
            virus[i] = false;
        }
    }

이제 바이러스가 있는 곳의 위치를 setVirus에 담아주고

바이러스가 퍼지는 것을 보여주면 된다.

static void spreadVirus(){
        visit = new int[N][N];
        Queue<Point> queue = new LinkedList<>();

        for(Point point : setVirus){
            queue.add(point);
            visit[point.x][point.y] = 1;
        }
        while(!queue.isEmpty()){
            Point point = queue.poll();

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

                if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
                if(map[nx][ny] != 1 && visit[nx][ny] == 0){
                    visit[nx][ny] = visit[point.x][point.y] + 1;
                    map[nx][ny] = 2;
                    queue.add(new Point(nx,ny));
                }
            }
        }
    }

Need Know

1. 브루트 포스
2. 조합

전체 코드 ( Java )

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;
    static int M;
    static int[][] map;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<Point> canVirus = new ArrayList<>();
    static ArrayList<Point> setVirus;
    static int[][] visit;
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }
    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int k=0; k<N; k++){
                map[i][k] = Integer.parseInt(st.nextToken());
                if(map[i][k] == 2){
                    canVirus.add(new Point(i,k));
                    map[i][k] = 0;
                }
            }
        }
    }
    static void solve() throws IOException {
        permutation(canVirus.size(), M, 0, new boolean[canVirus.size()]);
        if(ans == Integer.MAX_VALUE) bw.write(-1+"");
        else bw.write((ans-1) +"");
    }
    static void permutation(int n, int r, int peek, boolean[] virus){
        if(r == 0){
            setVirus = new ArrayList<>();
            for(int i=0; i<canVirus.size(); i++) {
                if(virus[i]){
                    setVirus.add(new Point(canVirus.get(i).x, canVirus.get(i).y));
                    map[canVirus.get(i).x][canVirus.get(i).y] = 2;
                }
            }
            spreadVirus();
            ans = Math.min(getTime(),ans);

            for(int i=0; i<canVirus.size(); i++) {
                map[canVirus.get(i).x][canVirus.get(i).y] = 0;
            }
            return;
        }
        for(int i=peek; i<n; i++){
            virus[i] = true;
            permutation(canVirus.size(), r-1, i+1, virus);
            virus[i] = false;
        }
    }
    static void spreadVirus(){
        visit = new int[N][N];
        Queue<Point> queue = new LinkedList<>();

        for(Point point : setVirus){
            queue.add(point);
            visit[point.x][point.y] = 1;
        }
        while(!queue.isEmpty()){
            Point point = queue.poll();

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

                if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
                if(map[nx][ny] != 1 && visit[nx][ny] == 0){
                    visit[nx][ny] = visit[point.x][point.y] + 1;
                    map[nx][ny] = 2;
                    queue.add(new Point(nx,ny));
                }
            }
        }
    }
    static int getTime(){
        int ans = 0;
        for(int i=0; i<N; i++){
            for(int k=0; k<N; k++){
                if(map[i][k] == 0) {
                    return Integer.MAX_VALUE;
                }
                ans = Math.max(ans, visit[i][k]);
            }
        }
        return ans;
    }
}
class Point {
    int x,y;

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