백준 17141 - 연구소2

[문제 바로가기]

 

1. 유형

 BFS, 조합

 

2. 문제 접근

2-1. 설계

일단 설계부터 해봅시다.

위치의 조합 찾기

문제에서 2는 바이러스를 퍼트릴 수 있는 곳 입니다.

따라서 List에 2의 위치를 모두 넣어주고, 그 중에서 M개를 선택합니다.

 

List에 위치를 넣는 방법은 (r,c)를 넣어줘도 되고, 저는 인덱스 값만 넣어줬습니다.

예를들어 N=3이라면, 아래 그림처럼 나올 것이고. 인덱스8은 의 좌표는 (8/N, 8%N)이 됩니다.

0	1	2
3	4	5
6	7	8

 

bfs로 퍼뜨리기

bfs구현에서 특별한것은 없습니다. 총 탐색한 칸수를 카운트해주고,

bfs가 끝나고 카운트해준 값이 바이러스를 퍼뜨릴 칸수와 일치하면 정답을 갱신합니다.

M=1일때, 아래 인풋값을 가정합시다.

바이러스를 유출해야하는 칸수는 8입니다. 바이러스인 2를 벽(1)처럼 제외해주면 안됩니다.

2	0	0
0	0	0
2	2	2

 

 

3. 코드

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

public class Main {
	static int N, M, matrix[][], D[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }, answer = 2500, spreadNum;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		matrix = new int[N][N];
		spreadNum = 0;
		int blockNum = 0;
		List<Integer> L = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				matrix[i][j] = stoi(st.nextToken());
				if (matrix[i][j] == 1) {
					blockNum++;
				} else if (matrix[i][j] == 2) {
					L.add(i * N + j);
				}
			}
		}
		spreadNum = N * N - blockNum - M;
		dfs(0, L, new int[M], 0);
		if (answer == 2500)
			answer = -1;
		System.out.println(answer);
	}

	static void dfs(int aidx, List<Integer> L, int[] a, int start) {
		if (aidx == M) {
			bfs(a);
			return;
		}
		for (int i = start; i < L.size(); i++) {
			a[aidx] = L.get(i);
			dfs(aidx + 1, L, a, i + 1);
		}
	}

	static void bfs(int a[]) {
		Queue<int[]> q = new LinkedList<>();
		boolean v[][] = new boolean[N][N];
		for (int e : a) {
			q.add(new int[] { e / N, e % N, 0 });
			v[e / N][e % N] = true;
		}
		int cnt = 0, dist = 0;
		while (!q.isEmpty()) {
			int cur[] = q.poll();
			for (int k = 0; k < 4; k++) {
				int nr = cur[0] + D[k][0];
				int nc = cur[1] + D[k][1];
				if (nr < 0 || nr >= N || nc < 0 || nc >= N || v[nr][nc] || matrix[nr][nc] == 1)
					continue;
				cnt++;
				v[nr][nc] = true;
				q.add(new int[] { nr, nc, cur[2] + 1 });
				dist = Math.max(dist, cur[2] + 1);
			}
		}
		if (cnt == spreadNum) {
			answer = Math.min(answer, dist);
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}