[Algorithm] 백준 17142(BOJ 17142) 연구소 3 문제풀이! (Java)

---

안녕하세요 coding-knowjam입니다.

오늘은 백준 온라인 저지에 있는 17142번 연구소 3 문제를 풀어보겠습니다.

문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다.

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

 

1. 문제 설명

해당 문제는 많이 풀어봤던 BFS문제를 응용해서 풀면 되는 문제입니다.

기본적으로 문제에서 요구하는 바는 바이러스가 가장 빨리 퍼지는 최소의 시간을 구하는 것이기 때문에, 주어진 바이러스에서 활성 바이러스를 선택하는 모든 경우의 수를 고려해야 합니다.

모든 경우의 수마다 BFS를 수행하여 가장 빨리 바이러스가 퍼졌을 때를 찾으면 되는 문제입니다.

해당 요구사항을 구현할 때 주의할 점은 다음과 같습니다. 

• 비활성 바이러스는 활성 바이러스를 만나면 활성 바이러스가 된다.
• 예를 들어 2:활성, 1:벽, 0:빈칸, -1:비활성이라고 가정했을 때, 2 -1 -1 0 이런 식의 행이 존재한다면 빈칸에 바이러스가 퍼질 때까지 3초가 소요됩니다)

위의 사항을 고려하지 않고 단순히 벽이 아니면 지나가고 벽이면 안 지나가고 이런 식으로 구현하게 되면 통과하지 못하기 때문에 반드시 위의 사항을 고려해서 구현하시길 바랍니다.

그럼 코드를 살펴보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingknowjam.algorithm.boj;

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.TreeSet;

// 백준온라인저지 17142번 연구소3 문제 풀이
public class BOJ_17142 {

	static int N;
	static int M;
	static int blankCount = 0;
	static int[][] map;
	static int[][] visited;
	static int[] target;
	static int[] moveRow = {-1, 1, 0, 0};
	static int[] moveCol = {0, 0, -1, 1};
	static ArrayList<Virus> virusList = new ArrayList<>();
	static TreeSet<Integer> result = new TreeSet<>();

	public static void main(String[] args) throws IOException {
		// 정보 초기화
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] NM = br.readLine().split(" ");
		N = Integer.parseInt(NM[0]);
		M = Integer.parseInt(NM[1]);
		map = new int[N][N];
		visited = new int[N][N];
		target = new int[M];

		// 바이러스 위치, 초기 빈칸개수 정보 저장 및 맵 초기화
		for (int i = 0; i < N; i++) {
			String[] temp = br.readLine().split(" ");
			for (int j = 0; j < temp.length; j++) {
				int objectNumber = Integer.parseInt(temp[j]);
				if (objectNumber == 2) {
					virusList.add(new Virus(i, j, 0));
				}
				if (objectNumber == 0) {
					blankCount++;
				}
				map[i][j] = objectNumber;
			}
		}
		
		// 빈칸이 하나도 없으면 0초
		if (blankCount == 0) {
			System.out.println(0);
			return;
		}
		
		// 주어진 바이러스에서 n개의 바이러스 조합 찾아서 BFS수행(모든 경우의 찾기)
		DFS(0, 0);
		
		//결과 출력
		if (result.contains(-1)) {
			if (result.size() == 1) {
				System.out.println(-1);
				return;
			} else {
				result.remove(-1);
			}
		}
		System.out.println(result.first());
	}

	private static void DFS(int lev, int index) {
		// 하나의 조합이 완료된 경우 
		if (lev == M) {
			// BFS수행을 위해 정보 초기홯
			int caseResult = 0;
			int caseBlankCount = blankCount;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					visited[i][j] = map[i][j];
				}
			}
			// 큐에 바이러스 넣기
			Queue<Virus> q = new LinkedList<>();
			for (int i = 0; i < target.length; i++) {
				Virus virus = virusList.get(target[i]);
				q.offer(new Virus(virus.row, virus.col, virus.timeCount));
			}
			
			//BFS 수행
			queueLoopOut:
			while (!q.isEmpty()) {
				Virus virus = q.poll();
				for (int i = 0; i < 4; i++) {
					int nr = virus.row + moveRow[i];
					int nc = virus.col + moveCol[i];
					if (nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc] == 1|| visited[nr][nc] == 3) {
						continue;
					}
					if(visited[nr][nc] == 0){
						caseBlankCount--;
					}
					q.offer(new Virus(nr, nc, virus.timeCount + 1));
					visited[nr][nc] = 3;
					caseResult = Math.max(caseResult, virus.timeCount + 1);
					if (caseBlankCount == 0) {
						break queueLoopOut;
					}
				}
			}
			if (caseBlankCount != 0) {
				caseResult = -1;
			}
			result.add(caseResult);
			return;
		}

		// 모든 경우의 수 조합 생성
		for (int i = index; i < virusList.size(); i++) {
			target[lev] = i;
			DFS(lev + 1, i + 1);
		}
	}

	// 바이러스 클래스
	static class Virus {
		int row;
		int col;
		int timeCount = 0;	// 몇초에 생성된 바이러스인지 체크를 위한 변수

		public Virus(int row, int col, int timeCount) {
			this.row = row;
			this.col = col;
			this.timeCount = timeCount;
		}
	}
}

 

모든 코드에 주석을 달기에는 설명이 너무 많아져서 로직의 중요한 부분에만 주석을 달아놓았습니다.

DFS로 모든 조합을 찾아가면서 BFS를 수행하므로 잘 이해가 안 가실 수도 있겠지만, 예시 데이터를 넣어서 한 사이클만 확인해보시면 어떻게 흘러가는지 쉽게 알 수 있을 거라 생각합니다.

감사합니다.

---