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

@조합, BFS / 45m

이번이 3번째 풀이

무난한 문제인데, 조건 하나때문에 틀려서 다시 풀었다.

 

 

문제 링크

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

17142번: 연구소 3

 

세달 전에도 풀었던 문제인데, 그때도 삽질하고 지금도 삽질..ㅎㅎ

이전 풀이

https://buddev.tistory.com/34

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

 

 

구현 방법

1. 맵을 입력받을 때 비활성 바이러스의 위치를 ArrayList에 넣어준다.

2. ArrayList의 개수(==바이러스의 개수)에서 M개를 고르는 조합을 만든다.

3. 조합을 다 고르고 나서 고른 바이러스들을 Queue에 넣어서 BFS로 퍼트려준다.

(이때 나는 활성 바이러스는 3부터 값을 매겼다. 그리고 시간을 계산할때는 -3을 해줘서 계산했다.)

이때, 가장 큰 시간을 계속 체크해준다

4. 바이러스가 다 퍼졌는지 체크해서

1) 다 퍼졌다면 3번에서 체크한 시간을 최솟값과 비교해서, 더 짧은 시간 안에 퍼졌다면 갱신해준다

2) 퍼지지 않은 곳이 있다면 -1을 return

 

 

 

삽질 포인트

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

이 말 때문에 많이 헷갈렸는데,

비활성 바이러스를 아예 지나지 않게 해도 안되고

이미 바이러스가 다 퍼진 상태인데 비활성 바이러스를 지나면서 시간이 늘어나도 안된다.

그래서, 비활성 바이러스를 Q에 넣기는 하되, 비활성 바이러스를 지날 때는 시간의 최댓값을 갱신하지 않는다

이렇게 if문을 추가했더니 정상적으로 작동했다.

 

그리고 예제 7의 빈 칸이 하나도 없는 경우를 대비한 예외 처리를 따로 해줘야 하나 고민했는데(아래에서 주석 처리한 부분),

이렇게 비활성 바이러스에 대한 처리를 해주면 별도로 예외 처리를 하지 않아도 괜찮다!

 

 

코드

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

public class Main_200530 {
	
	static class Node {
		int x, y, t;
		Node (int x, int y, int t) {
			this.x = x;
			this.y = y;
			this.t = t;
		}
	}
	static int N, M, size, map[][], copyMap[][], min = Integer.MAX_VALUE, nowMax, combi[];
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	static ArrayList<Node> virus = new ArrayList<Node>();
	static Queue<Node> q = new LinkedList<Node>();

	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];
		copyMap = new int[N][N];
		
//		boolean emptyExist = false;
		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)
					virus.add(new Node(i, j, 3));
//				if (map[i][j] == 0)
//					emptyExist = true;
			}
		}
//		if (!emptyExist) {
//			System.out.println(0);
//			return;
//		}

		size = virus.size();
		combi = new int[M];
		combi(M, 0, 0);
		if (min == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(min);
	}

	private static void combi(int n, int k, int idx) {
		if (n == k) {
			for (int i = 0; i < N; i++)
				copyMap[i] = map[i].clone();
			
			nowMax = 0;
			q.clear();
			for (int i = 0; i < n; i++) {
				q.add(new Node(virus.get(combi[i]).x, virus.get(combi[i]).y, 3));
				copyMap[virus.get(combi[i]).x][virus.get(combi[i]).y] = 3;
			}
			bfs();
			if (!zeroExistCheck())
				if (min > nowMax)
					min = nowMax;
			return;
		}
		for (int i = idx; i < size; i++) {
			combi[k] = i;
			combi(n, k + 1, i + 1);
			combi[k] = -1;	//사실 안해줘도 되긴 함 
		}
	}

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

	private static void bfs() {
		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];
				int nt = temp.t + 1;
				
				if (nx < 0 || nx >= N || ny < 0 || ny >= N || copyMap[nx][ny] == 1 || copyMap[nx][ny] > 2)
					continue;

				//비활성바이러스일때는 q에 넣어주되 시간체크는 하지 않는다 
				if (copyMap[nx][ny] != 2)
					if (nowMax < nt - 3) nowMax = nt - 3;
				
				q.add(new Node(nx, ny, nt));
				copyMap[nx][ny] = nt;
			}
		}
	}
}

오늘, 3달 전, 8달 전..ㅎㅎ

그래도 처음 풀 때보다 훨씬 빨리 풀었다!ㅎㅎ