[백준] 17142.연구소3 (java) / 백트래킹, DFS, BFS, 조합

@백트래킹, DFS, BFS, 조합 / 43m (필기 11분, 디버깅 8분 포함)

기본 문제인데 조건을 하나 놓쳐서

그 부분 고치고 무난하게 풀었다.

 

문제 링크

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

17142번: 연구소 3

 

구현 방법

큰 틀은 백준 14502.연구소 와 비슷하다.

1. 바이러스들 중 활성 바이러스로 만들 M개를 골라 놓고

2. copyMap을 만들어서 거기에 바이러스를 퍼트리고

3. 확산 시간을 구하고, 최소 시간을 갱신한다.

 

삽질 포인트

문제가 됐던 부분은 2번인데,

활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

이 부분을 놓쳤다.

 

2번에서 바이러스가 퍼질 수 있는 경우는

1) 빈 칸이거나

2) 비활성 바이러스거나

이 둘 중 하나이다. 즉, 처음 풀었을때는 1)만 생각해서 틀렸다.

 

나는 바이러스를 퍼뜨릴 때 copyMap의 매 칸에 시간을 표시해 줬다.

문제는 이 방식으로 하면 2초대에 바이러스가 퍼져서 값이 2인 건지, 아니면 바이러스가 들어있어서 값이 2인 건지가 구분되지 않는다.

즉, copyMap만으로는 비활성 바이러스를 찾아 낼 수 없다.

 

그래서 조건에서 if(copyMap[][] == 2 && map[][] == 2) 이 부분을 추가했다.

이렇게 하면 이 칸이 원래부터 바이러스였는지를 확인 할 수 있다.

 

 

이 부분을 고쳐서 냈는데도 또 틀렸습니다가 떴다.

이유는, 비활성 바이러스가 활성 바이러스로 바뀔 때, 큐에 넣을 시간을 1로 설정해 줬기 때문이었다.

만약 3초에 비활성 바이러스가 활성 바이러스로 바뀐다면, 큐에 들어가는 이 바이러스의 시간은 4가 되어야 한다.

이 부분을 수정해 줬더니 통과했다.

 

 

코드 개선

여기서는 바이러스들 중에, 활성화 시킬 M개를 고르는 것이기 때문에

바이러스를 LinkedList에 담아 놓고, 이 크기만큼 boolean[] combi 배열을 만들어서

평소에 쓰던 재귀 조합을 이용해서 다시 풀어봤더니 시간이 70ms가량 줄고, 가독성도 향상됐다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	
	private static class Node {
		int x, y, t;
		Node (int x, int y, int t) {
			this.x = x;
			this.y = y;
			this.t = t;
		}
	}
	private static int N, M, min = Integer.MAX_VALUE, map[][], copyMap[][];
	private static boolean combi[];
	private static int[] dx = {0, -1, 0, 1}, dy = {1, 0, -1, 0};
	private static LinkedList<Node> list;
	private static Queue<Node> q;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		list = new LinkedList<Node>();
		q = new LinkedList<Node>();
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		copyMap = new int[N][N];
		
		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] == 2) list.add(new Node(i, j, 1));
			}
		}
		
		combi = new boolean[list.size()];
		combi(0, 0);
		
		if (min == Integer.MAX_VALUE) System.out.println("-1");
		else System.out.println(min);
	}

	private static void combi(int k, int idx) {
		if (M == k) {
			makeCopyMap();
			addQueueVirus();
			int time = spreadVirus();
			if (checkTime())
				if (min > time)
					min = time;
		}
		
		for (int i = idx; i < combi.length; i++) {
			combi[i] = true;
			combi(k + 1, i + 1);
			combi[i] = false;
		}
	}

	private static boolean checkTime() {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				if (copyMap[i][j] == 0)
					return false;
		
		return true;
	}

	private static int spreadVirus() {
		int time = 0;
		while (!q.isEmpty()) {
			Node temp = q.poll();
			
			for (int d = 0; d < 4; d++) {
				int nx = temp.x + dx[d];
				int ny = temp.y + dy[d];
				
				if (nx < 0 || nx >= N || ny < 0 || ny >= N || copyMap[nx][ny] == 1 || copyMap[nx][ny] >= 3) continue;
				
				if (copyMap[nx][ny] == 2 && map[nx][ny] == 2) {
					copyMap[nx][ny] = 3;
					q.add(new Node(nx, ny, temp.t + 1));
				} else if (copyMap[nx][ny] == 0) {
					copyMap[nx][ny] = temp.t;
					q.add(new Node(nx, ny, temp.t + 1));
					if (time < temp.t) time = temp.t;
				}
			}
		}
		return time;
	} 

	private static void addQueueVirus() {
		for (int i = 0; i < combi.length; i++) {
			if (combi[i]) {
				q.add(list.get(i));
				copyMap[list.get(i).x][list.get(i).y] = 3;
			}
		}
	}

	private static void makeCopyMap() {
		for (int i = 0; i < N; i++)
			copyMap[i] = map[i].clone();
	}
}