BOJ - 연구소 3 17142번 (JAVA)

❓ 문제 - 백준 연구소 3 17142번 - JAVA 풀이법

 

출처 

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

17142번: 연구소 3

 

 

📝 문제해결법

1. 이 문제는 DFS(조합) + BFS로 풀었다.

• 바이러스 중 M개의 활성 바이러스로 시킬 것들의 조합을 만든 후 해당 조합에서 다른 바이러스가 아닌 곳까지 다 퍼트리는데 얼만큼 시간이 걸리는지의 최솟값을 계속 갱신한다.
• BFS 내에서는 선택된 바이러스를 활성으로 만들고 큐에 넣고 인접한 4방향으로 탐색하면서 만약 바이러스가 아닌 곳(0)이라면 퍼트리는 시간을 해당 노드를 방문하는데 걸리는 거리만큼 계속 최대값 갱신해준다. 만약 비활성 바이러스인 곳을 만났다면 큐에만 넣어주고 방문처리 해준다.

 

2. 느낀점

• 처음에 비활성 바이러스와 바이러스가 아닌 빈칸의 차이점을 몰랐는데 그냥 비활성 바이러스도 하나의 빈칸으로 취급하고, 바이러스를 다 퍼트리는데 걸리는 최대 시간을 반영할 때는 빈칸에 도달했을 때만 맞춰서 구현해주면 됐다..!
• 앞으로 잘 구현한 것 같은데 테케에 맞지 않는다면 테케 하나씩 분석해서 왜 이런 출력값이 나오는지 역 분석해서 맞춰서 코딩하자 ! 그리고.. 문제를 잘 읽자 ^_^

 

💻 소스코드

// BOJ - 연구소3(17142번)
// DFS + BFS
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.StringTokenizer;

public class Main_17142 {
	public static int n, m, ans, zero_cnt;
	public static int[][] map;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static class Node {
		int x;
		int y;
		int dis;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		public Node(int x, int y, int dis) {
			this.x = x;
			this.y = y;
			this.dis = dis;
		}

	}
	public static ArrayList<Node> virus;
	
	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());
		map = new int[n][n];
		ans = Integer.MAX_VALUE;
		virus = new ArrayList<>();
		zero_cnt = 0;
		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));
				} else if(map[i][j] == 0) {
					zero_cnt++;
				}

			}
		}
		
		dfs(0, 0, new int[m]);
		
		if(ans == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(ans);
		}
		
	}
	
	public static void dfs(int depth, int start, int[] arr) {
		if(depth == m) {
			int time = bfs(arr);
			if(time != -1) {
				ans = Math.min(ans, time);
			}
			return;
		}
		
		for(int i=start;i<virus.size();i++) {
			arr[depth] = i;
			dfs(depth+1, i+1, arr);
		}
	}
	
	public static int bfs(int[] arr) {
		Queue<Node> q = new LinkedList<>();
		boolean[][] visited = new boolean[n][n];
		for(int a:arr) {
			Node node = virus.get(a);
			node.dis = 0;
			visited[node.x][node.y] = true;
			q.add(node);
		}
		int time = 0;
		int cnt = 0;
		while(!q.isEmpty()) {
			Node node = q.poll();
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
				if(!visited[nx][ny]) {
					if(map[nx][ny] == 0) {
						visited[nx][ny] = true;
						cnt++;
						time = Math.max(time, node.dis+1);
						q.add(new Node(nx, ny, node.dis+1));
					} else if(map[nx][ny] == 2){
						visited[nx][ny] = true;
						q.add(new Node(nx, ny, node.dis+1));
					}
				}
			}
			}
		}
		
		if(cnt != zero_cnt) return -1;
		
		return time;
		
		
	}

}