문제
https://www.acmicpc.net/problem/17142
풀이 과정
바이러스 중에서 M개를 선택하는 조합 + 각 바이러스를 빈칸 또는 비활성 바이러스로 퍼뜨리는 BFS탐색으로 풀이할 수 있다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N, M, blank, min;
static int[][] map;
static List<Node> virus;
static class Node{
int x, y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
try{
init();
if(blank == 0){
min = 0;
}
else{
selectVirus(0, 0, new Node[M]);
}
}catch (Exception e){
e.printStackTrace();
}
System.out.println((min == Integer.MAX_VALUE) ? -1 : min);
}
public static void init() 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];
virus = new ArrayList<>();
min = Integer.MAX_VALUE;
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());
if(map[i][j] == 0){
blank++;
}
else if(map[i][j] == 2){
virus.add(new Node(i, j));
}
}
}
}
public static void selectVirus(int cnt, int idx, Node[] selectedVirus){
if(cnt >= M){
getMinTime(selectedVirus);
return;
}
for(int i=idx; i<virus.size(); i++){
selectedVirus[cnt] = virus.get(i);
selectVirus(cnt + 1, i + 1, selectedVirus);
}
}
public static void getMinTime(Node[] viruses){
//1이 아닌 모든 곳에 퍼트리기 가능
//2만 남았으면 cnt할 필요 없음
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
Queue<Node> q = new LinkedList<>();
boolean[][] visited = new boolean[N][N];
//1. virus 위치 넣기
for(Node virus : viruses){
visited[virus.x][virus.y] = true;
q.add(virus);
}
//2. 퍼트리기
int result = 0, infected = 0;
while(!q.isEmpty()){
int size = q.size();
while(size-- > 0){
Node now = q.poll();
if(map[now.x][now.y] == 0){
infected++;
}
for(int i=0; i<4; i++){
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if(nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny]) continue;
visited[nx][ny] = true;
if(map[nx][ny] != 1){
q.add(new Node(nx, ny));
}
}
}
//다 감염시켰으면 종료
if(infected == blank){
min = Math.min(min, result);
return;
}
result++;
}
}
}
여기서 조합을 구하고 BFS탐색을 하지 않고, BFS탐색을 한 후, 조합대로 계산하면 더 효율적으로 처리할 수 있다. 각 바이러스마다 한번의 BFS탐색만 거치도록 하는 것이다.
각 바이러스에서 빈 칸을 감염시키는 데 걸리는 시간을 각 칸에 미리 저장하고, 조합마다 M개의 바이러스 중 어느 바이러스가 해당 칸을 감염시키는 데 가장 적게 걸리는 지 구한다.
결과는 전체 빈 칸을 감염시키는 데 걸리는 최소 시간 중 가장 큰 값을 구하고, 여기서 가장 작은 값이 정답이 된다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N, M, blank, result;
static int[][] map;
static int[][][] distance;
static List<Node> viruses;
static class Node{
int x, y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
try{
init();
if(blank == 0){
result = 0;
}
else{
for(int i=viruses.size()-1; i>=0; i--){
updateDistance(i);
}
selectVirus(0, 0, new int[M]);
}
}catch (Exception e){
e.printStackTrace();
}
System.out.println((result == Integer.MAX_VALUE) ? -1 : result);
}
public static void init() 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];
viruses = new ArrayList<>();
result = Integer.MAX_VALUE;
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());
if(map[i][j] == 0){
blank++;
}
else if(map[i][j] == 2){
viruses.add(new Node(i, j));
}
}
}
distance = new int[viruses.size()][N][N];
}
public static void updateDistance(int idx){
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
Queue<Node> q = new LinkedList<>();
for(int i=0; i<N; i++){
Arrays.fill(distance[idx][i], Integer.MAX_VALUE);
}
//1. virus 위치 넣기
Node virus = viruses.get(idx);
distance[idx][virus.x][virus.y] = 0;
q.add(virus);
//2. 퍼트리기
while(!q.isEmpty()){
Node now = q.poll();
for(int i=0; i<4; i++){
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if(nx<0 || nx>=N || ny<0 || ny>=N || map[nx][ny]==1) continue;
if(distance[idx][nx][ny] == Integer.MAX_VALUE){
distance[idx][nx][ny] = distance[idx][now.x][now.y] + 1;
q.add(new Node(nx, ny));
}
}
}
}
public static void selectVirus(int cnt, int idx, int[] selectedVirus){
if(cnt >= M){
result = Math.min(result, getMinTime(selectedVirus));
return;
}
for(int i=idx; i<viruses.size(); i++){
selectedVirus[cnt] = i;
selectVirus(cnt + 1, i + 1, selectedVirus);
}
}
public static int getMinTime(int[] selectedVirus){
int maxDistance = 0;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(map[i][j] != 0) continue;
int min = distance[selectedVirus[0]][i][j];
for(int k=1; k<M; k++){
min = Math.min(min, distance[selectedVirus[k]][i][j]);
}
maxDistance = Math.max(maxDistance, min);
}
}
return maxDistance;
}
}
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Java] 백준 2138번 : 전구와 스위치 (0) | 2023.03.20 |
---|---|
[Java] 백준 14940번 : 쉬운 최단거리* (0) | 2023.03.19 |
[Java] 백준 2607번 : 비슷한 단어 (0) | 2023.03.14 |
[Java] 백준 9019번 : DSLR* (0) | 2023.03.13 |
[Java] 백준 1138번 : 한 줄로 서기* (0) | 2023.03.10 |