[BOJ/Java] 17142. 연구소 3

[BOJ/Java] 17142. 연구소 3

17142번: 연구소 3

---

문제 해석

이 문제에서는 연구소 내의 빈 칸에 바이러스를 퍼뜨려 모든 빈 칸을 감염시키는 최소 시간을 구하는 것이 목표다. 연구소는 정사각형 격자 모양으로, 바이러스는 비활성 상태에서 시작해 특정 위치에서 활성화될 수 있다. 활성화된 바이러스는 상하좌우로 퍼질 수 있으며, 빈 칸만 감염시킬 수 있다. 벽은 감염되지 않고, 활성화된 바이러스가 있는 위치로 다른 바이러스가 이동할 수 없다.

풀이 과정

제출된 Java 코드는 가능한 모든 바이러스 조합을 탐색하여 최적의 확산 시간을 계산한다. 이를 위해 먼저 바이러스를 활성화시킬 조합을 순열로 결정하고, 그 후 너비 우선 탐색(BFS)을 사용하여 바이러스가 퍼지는 시간을 계산한다.

 

• 데이터 입력: 연구소의 크기와 바이러스의 위치를 입력받는다.
• 순열 생성 (permutation 메소드): 활성화할 바이러스의 조합을 결정한다.
• BFS 탐색 (bfs 메소드): 선택된 바이러스에서 시작하여 연구소 전체에 바이러스를 퍼뜨리는 시간을 계산한다.
• 경계 및 조건 검사: 각 단계에서 벽이나 이미 방문한 위치를 건너뛰며, 모든 빈 칸이 감염될 때까지 탐색을 진행한다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No17142;

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	private int[][] graph; // 연구소의 맵
	private ArrayList<Virus> virusList; // 바이러스 위치 목록
	private int m, ans = Integer.MAX_VALUE, CNT = 0; // 활성화할 바이러스 수, 최소 시간, 빈 칸의 수
	private static final int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; // 이동 가능한 방향
	private int[] sel; // 선택된 바이러스 인덱스
	private boolean[][] visited; // 방문 여부 체크

	public static void main(String[] args) throws IOException {
		new Main().sol();
	}

	class Virus {
		int x, y, time; // 바이러스의 위치와 확산 시간

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

	private void sol() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		graph = new int[n][n];
		virusList = new ArrayList<>();
		for (int i = 0; i < graph.length; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < graph.length; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
				if (graph[i][j] == 2) {
					virusList.add(new Virus(i, j, 0)); // 바이러스 위치 저장
				} else if (graph[i][j] == 0) {
					CNT++; // 빈 칸의 수 계산
				}
			}
		}

		getAns();

		sb.append(ans); // 결과 출력
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private void getAns() {
		if (CNT != 0) {
			sel = new int[m];
			permutation(0, 0);
			ans = ans == Integer.MAX_VALUE ? -1 : ans;
		} else {
			ans = 0;
		}
	}

	private void permutation(int k, int v) {
		if (k == m) {
			int res = bfs();
			res = res == -1 ? Integer.MAX_VALUE : res;
			ans = Math.min(ans, res);
			return;
		}

		for (int i = 0; i < virusList.size(); i++) {
			if ((v & (1 << i)) == 0) {
				sel[k] = i;
				permutation(k + 1, v |= 1 << i);
			}
		}
	}

	private int bfs() {
		Queue<Virus> queue = new ArrayDeque<>();
		visited = new boolean[graph.length][graph.length];
		int cnt = CNT;

		for (int s : sel) {
			queue.offer(virusList.get(s));
			visited[virusList.get(s).x][virusList.get(s).y] = true;
		}

		while (!queue.isEmpty()) {
			Virus v = queue.poll();

			if (v.time+1 >= ans) // 현재 최소 시간보다 크면 중단
				return -1;

			for (int d = 0; d < direction.length; d++) {
				int nx = v.x + direction[d][0];
				int ny = v.y + direction[d][1];

				if (checkStatus(nx, ny)) {
					if (graph[nx][ny] == 0)
						cnt--;
					visited[nx][ny] = true;
					queue.offer(new Virus(nx, ny, v.time + 1));

					if (cnt == 0)
						return v.time + 1; // 모든 빈 칸이 감염된 경우
				}
			}
		}

		return -1; // 감염되지 않은 빈 칸이 남아있는 경우
	}

	private boolean checkStatus(int nx, int ny) {
		return 0 <= nx && nx < graph.length && 0 <= ny && ny < graph.length && graph[nx][ny] != 1 && !visited[nx][ny];
	}
}

시간 복잡도 분석

이 알고리즘은 순열과 BFS를 결합하여 사용하므로, 복잡도는 상당히 높다. 순열 생성의 복잡도는 O(m!)이며, 각 순열에 대한 BFS 탐색은 O(n^2)이다. 따라서 전체 시간 복잡도는 O(m!×n^2)이 될 수 있다.

느낀점

이 문제를 통해 조합적 탐색과 시뮬레이션을 결합한 복잡한 문제를 해결하는 방법을 배울 수 있었다. 복잡한 문제에서도 체계적인 접근과 정확한 알고리즘 선택이 중요함을 확인할 수 있었다.