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

문제 접근

N * N 크기의 연구소에서 M개의 바이러스를 활성화 시켜, 모든 빈칸(0)에 바이러스를 퍼트리는 데 걸리는 최소 시간을 구하는 시뮬레이션 문제이다.

연구소의 상태값

• 0 : 빈칸 (바이러스가 퍼져야 할 목표 타겟)
• 1 : 벽 (바이러스가 이동 불가능한 지점)
• 2 : 바이러스 위치 (이 중 M개를 골라 활성화 해야함)

제약 조건

• 바이러스는 1초에 상하좌우 인접한 칸으로 동시에 퍼져나간다.
• 활성화된 바이러스가 비활성 바이러스 칸에 도달하면 비활성 바이러스도 활성화된다.
• 모든 지역에 바이러스를 퍼트릴 수 없으면 -1을 출력

문제 설계

전체 프로세스

1. 입력 및 초기화 : int N, M과 연구소 상태(int[][] lab)를 입력 받는다. 입력 받는 과정에서 바이러스의 위치(List<int[]> virus)와 벽의 위치(List<int[]> walls)를 따로 저장하여 관리 효율을 높임

2. 조합 생성 : 전체 바이러스 중 활성화 시킬 M개의 바이러스를 선택 -> DFS를 이용한 백트래킹으로 모든 경우의 수를 생성한다.

3. 시뮬레이션 : 생성된 각 조합에 대해 바이러스 확산 시뮬레이션을 실행

• 선택된 M개의 바이러스 위치를 BFS를 위한 Queue에 넣는다.
• BFS를 통해 1초 단위로 바이러스가 퍼져나가는 과정을 시뮬레이션 한다.
• 확산이 진행될 때마다, 모든 빈칸의 감염 여부를 체크(check()) 한다.
• 모든 빈 칸이 감염되었다면, 그때까지 걸린 시간을 반환하고, 해당 조합의 시뮬레이션을 종료한다.

4. 최소 시간 갱신 : 각 조합의 시뮬레이션 결과를 전역 변수 result와 비교하여 더 작은 값으로 갱신

5. 결과 출력 : 모든 탐색이 끝난 후 result에 저장된 값을 출력 초기값을 -1로 설정하여 바이러스가 퍼질 수 없는 경우 -1를 출력하도록 설계

자료구조 및 함수 정의

전역 변수

• int N, M : 문제에서 주어진 연구소의 크기와 활성화된 바이러스 개수
• int[][] lab : 원본 연구소의 상태 저장할 2차원 배열
• int result : 최소 시간을 저장할 정수 변수 (초기값 -1)
• List<int[]> virus : 모든 바이러스의 좌표를 모두 저장하는 리스트
• List<int[]> walls : 벽의 좌표를 저장하는 리스트
• List<Integer> selected : virus 리스트에서 선택된 M개의 바이러스 인덱스를 저장할 리스트

함수

• dfs(int depth, int idx) : 바이러스 조합을 생성하는 재귀함수
  • depth : 현재까지 선택한 바이러스 개수
  • idx : 탐색을 시작할 virus 리스트의 인덱스
  • depth가 M이 되면 bfs()를 호출하여 시뮬레이션 시작
• bfs() : 선택된 바이러스 조합으로 확산을 시뮬레이션하고 걸린 시간을 반환하는 함수
  • ArrayDeque<int[]> queue : BFS 탐색을 위한 큐
  • int[][] visited : 방문 여부 및 시간, 상태를 기록할 2차원 배열
    • 0 : 미방문 빈 칸, 1 : 벽, 2 : 활성 감염, 3 : 비활성 바이러스
  • check(int[][] visited) : visited 배열을 보고 모든 빈 칸이 감염되었는지 확인하는 함수

설계 근거

M개의 바이러스 활성화(DFS)

위 문제는 여러 바이러스 후보 중 M개를 활성화하는 것 즉 순서에 상관없이 M개를 뽑는 대표적인 조합 문제이다. 가능한 모든 조합을 탐색하는 가장 직관적이고 효과적인 방법은 DFS를 이용한 백트래킹이다. 재귀 호출을 통해 바이러스를 하나씩 선택(add)하고, 해당 경우의 수 탐색이 끝나면 선택 취소(remove)하며 모든 조합을 효율적으로 만들 수 있다.

최단 시간(BFS)

바이러스가 모든 빈 칸에 퍼지는 최소 시간을 구하는 것은 그래프에서 최단 거리를 찾는 문제와 같다. 연구소의 각 칸을 정점(Vertex)으로 인접한 칸으로의 이동을 간선(Edge)로 생각할 수 있다.
모든 간선의 가중치가 1로 동일한 상황에서 최단 거리를 찾는 데 가장 적합한 알고리즘은 BFS이기 때문에 BFS를 통해 시작점으로부터 거리가 가까운 순서대로 탐색을 진행하며 목표 상태에 도달했을 때의 탐색 깊이가 곧 최소 시간이 된다.

결론

DFS로 어떻게 바이러스를 놓을지에 대한 모든 경우의 수를 찾고, 각 경우의 수에 대해 BFS로 최소 확산 시간을 계산한 뒤, 그 중 가장 작은 값을 찾는 것이 가장 직관적인 접근법이라 생각한다.

구현 코드

초기 설정

package Algorithm.BFS.BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 연구소3
 * 바이러스를 퍼트리는 최소시간 구하기
 */
public class gold3_17142 {
	static int N, M;
	static int[][] matrix;
	static int result;
	static List<int[]> virus;
	static List<int[]> walls;
	static List<Integer> selected;
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		matrix = new int[N][N];
		virus = new ArrayList<>();
		walls = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			st= new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int num = Integer.parseInt(st.nextToken());
				matrix[i][j] = num;
				if (num == 2) {
					virus.add(new int[] {i, j});
				} else if (num == 1) {
					walls.add(new int[] {i, j});
				}
			}
		}
		
		selected = new ArrayList<>();
		result = -1;
		
		dfs(0, 0);
		
		System.out.println(result);
	}
}
  

• 입력을 받고, 동시에 바이러스와 벽의 좌표를 각각 virus, walls 리스트에 저장
• 모든 입력 처리가 끝난 후 dfs(0, 0)을 호출하여 M개의 바이러스를 선택하는 조합 생성을 시작

조합 생성(dfs)

public static void dfs(int depth, int idx) {
	if (depth == M) {
		int t = bfs();
		
		if (t != -1 && result == -1) {
			result = t;
		} else if (t != -1 && result != -1) {
			result = Math.min(result, t);
		}
		
		return;
	}
	
	if (idx == virus.size()) {
		return;
	}
	
	selected.add(idx);
	dfs(depth + 1, idx + 1);
	
	selected.remove(selected.size() - 1);
	dfs(depth, idx + 1);
}

• depth가 M이 되면, 하나의 조합이 완성된 것 이 때 bfs()를 호출해 시뮬레이션을 돌리고 결과를 result에 갱신
• selected.add(idx)로 현재 바이러스를 선택하고 다음 탐색을 진행,
• selected.remove()를 통해 선택을 취소하고 다음 경우의 수를 탐색하는 백트래킹 구현

바이러스 확산 시뮬레이션(bfs)

public static int bfs() {
	ArrayDeque<int[]> queue = new ArrayDeque<>();
	int[][] visited = new int[N][N];
	for (int[] wall : walls) {
		visited[wall[0]][wall[1]] = 1;
	}
	
	for (int[] v : virus) {
		visited[v[0]][v[1]] = 3;
	}
	
	for (int num : selected) {
		int[] v = virus.get(num);
		visited[v[0]][v[1]] = 2;
		queue.offer(v);
	}
	
	int t = 0;
	
	if (check(visited)) {
		return t;
	}
	
	
	while (!queue.isEmpty()) {
		int size = queue.size();
		for (int i = 0; i < size; i++) {
			int[] cur = queue.poll();
			int r = cur[0];
			int c = cur[1];
			
			for (int dir = 0; dir < 4; dir++) {
				int nr = r + dr[dir];
				int nc = c + dc[dir];
				
				if (nr >= 0 && nr < N && nc >= 0 && nc < N && (visited[nr][nc] == 0 || visited[nr][nc] == 3)) {
					visited[nr][nc] = 2;
					queue.offer(new int[] {nr, nc});
				}
			}
		}
		t++;
		if (check(visited)) {
			return t;
		}
	}
	
	return -1;
}

• visited 배열을 통해 벽, 비활성 바이러스, 감염된 칸을 구분
• while 루프 안에서 size를 고정하고 for문을 돌리는 패턴은 BFS에서 레벨별탐색을 구현하는 방법 중 하나이다.
• 매 초(t++)가 지날 때마다 check() 함수로 목표 달성 여부를 확인하여 불필요한 탐색을 줄인다.

바이러스 확산 체크(check)

public static boolean check(int[][] visited) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] == 0) {
				return false;
			}
		}
	}
	
	return true;
}