[백준 - java] 17142번 : 연구소 3

문제

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

설명

조합과 BFS를 이용해 문제를 풀었다!

1. 조합을 통해 M개의 활성 바이러스를 선택
2. 활성 바이러스를 큐에 넣고, 방문처리 해줌
3. BFS를 통해 빈 칸에 바이러스를 퍼뜨림
4. 빈 칸에 바이러스를 다 퍼뜨린 경우 최단 시간 갱신 후 BFS 종료

// 처음 문제를 풀 때는 아래와 같이 활성 바이러스가 있는 곳은 3을 저장했다.
for (int i = start; i < virusList.size(); i++) {
	map[i][j] = 3;
    selectActiveVirus(i + 1, depth + 1);
    map[i][j] = 2;
}

// 그리고 bfs함수 안에서 활성 바이러스 위치를 큐에 넣어줄 때 이렇게 넣었다.
for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		if (map[i][j] == 3) {
			q.add(new Virus(i, j, 0));
            visited[i][j] = true;
        }
}

// 그런데 나중에 생각해보니 굳이 맵을 한 번 더 돌면서 큐에 넣어줄 필요 없이 아래 코드와 같이 바꿔주는게 더 효율적일 것 같아 코드를 수정했다!

// 활성 바이러스 선택
for (int i = start; i < virusList.size(); i++) {
	virus[depth] = virusList.get(i);
    selectActiveVirus(i + 1, depth + 1);
}

// 활성 바이러스 위치 큐에 넣어줌
for (Virus v : virus) {
	q.add(new Virus(v.x, v.y, 0));
	visited[v.x][v.y] = true;
}

소스코드

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

class Virus {
    int x;
    int y;
    int time;

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

public class Main {

    // 상하좌우
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };

    static int N, M;
    static int[][] map; // 0은 빈 칸, 1은 벽, 2는 바이러스의 위치
    static ArrayList<Virus> virusList = new ArrayList<>();
    
    static Virus[] virus;

    static int empty = 0;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        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];
        virus = new Virus[M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()); // 0은 빈 칸, 1은 벽, 2는 바이러스

                if (map[i][j] == 2) {
                    virusList.add(new Virus(i, j, 0));
                }

                if (map[i][j] == 0) {
                    empty++;
                }
            }
        }

        // 빈 칸이 없을 경우 바이러스가 이미 다 퍼져있는 것이기 때문에 0 출력
        if (empty == 0) {
            System.out.println(0);
        } else {
            selectActiveVirus(0, 0);
            System.out.println(answer == Integer.MAX_VALUE ? -1 : answer); // 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1 출력
        }

    }

    // 조합을 통해 활성 바이러스가 위치할 수 있는 곳 선택
    private static void selectActiveVirus(int start, int depth) {
        // M개의 활성 바이러스를 다 선택한 경우 bfs 실행
        if (depth == M) {
            bfs(empty);
            return;
        }

        for (int i = start; i < virusList.size(); i++) {
            virus[depth] = virusList.get(i);
            selectActiveVirus(i + 1, depth + 1);
        }
    }

    // bfs를 통해 바이러스 퍼뜨림
    private static void bfs(int cnt) {
        Queue<Virus> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][N]; // 바이러스 확산 여부 저장
        
        // 활성 바이러스 위치 큐에 넣어줌
        for (Virus v : virus) {
        	q.add(new Virus(v.x, v.y, 0));
        	visited[v.x][v.y] = true;
        }

        while (!q.isEmpty()) {
            Virus cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                // 범위를 벗어나거나 이미 방문 했거나 벽인 경우 다음으로 넘어감
                if (!isRange(nx, ny) || visited[nx][ny] || map[nx][ny] == 1) {
                	continue;
                }
                
                // 비활성 바이러스가 있는 곳은 활성 바이러스로 변하기 때문에 if문에 넣지 않음
                q.add(new Virus(nx, ny, cur.time + 1));
                visited[nx][ny] = true;
                
                // 빈 칸일 경우 바이러스를 퍼뜨리기 때문에 cnt를 감소시킴
                if (map[nx][ny] == 0) {
                	cnt--;
                }
                
                // 바이러스를 다 퍼뜨린 경우(빈 칸이 다 없어진 경우) 최단 시간 갱신 후 종료
                if (cnt == 0) {
                	answer = Math.min(answer, cur.time + 1);
                	return;
                }

            }
        }

    }
    
    private static boolean isRange(int x, int y) {
    	return x >= 0 && x < N && y >= 0 && y < N;
    }

}

GITHUB

https://github.com/MinchaeKwon/BOJ/blob/master/BOJ%2317142/src/Main.java