[Java] 백준 연구소 3

문제

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

17142번: 연구소 3

brute force 를 구현하는 문제

 

풀이

일단 나이브하게 모든 바이러스의 조합을 구하고 완전탐색을 하여 가장 낮은 것을 출력하는 구현 문제이다.

 

풀이 알고리즘은 다음과 같다.

1. 놓을 수 있는 바이러스의 위치 조합(combination) 을 구한다. 
2. 해당 조합에서 바이러스를 활성화시키고 BFS 탐색을 한다.
3. 출력으로 -1 이 나온 경우를 제외하고 최솟값을 구한다.
4. 모든 경우가 -1 이면 -1을 출력한다. 

 

바이러스의 조합은 재귀 함수로 구현하였다.  재귀 끝에 도달하면, 링크드 리스트에 추가하는 방식인데 메모리에 새로운 배열 new 안해주고  단순히 배열 이름을 추가했다가 LinkedList<> 모든 값이 복제가 되는 에러가 났다. 따라서 IntStream 클래스를 사용하여 new 연산을 실행하였다.

	public void getVirusCombination(int start, int M, int L, ArrayList<int[]> virusLocate, LinkedList<int[]> virusL,
			int[] arr, boolean[] visit) {
		if (L == M) {
			int a[] = IntStream.of(arr)
					.map(x->x)
					.toArray();
			virusL.add(a);//deep copy 안하고 shallow copy를 하면 안됨 주의
		}
		if (start == virusLocate.size() || L == M)
			return;
		for (int i = start; i < virusLocate.size(); i++) {
			if (!visit[i]) {
				arr[L] = i;
				visit[i] = true;
				getVirusCombination(i + 1, M, L + 1, virusLocate, virusL, arr, visit);
				visit[i] = false;
			}
		}
	}

조합을 구했으면, 바이러스 놓일 수 있는 모든 캐이스의 최솟값을 구한다. 바이러스는 병렬적으로 동시에 활성화됨으로 DFS 아닌 BFS 레벨 탐색으로 구현하였다. 

public int active_Virus(int m[][], int[] Pos, ArrayList<int[]> V, int nonvirus) {

		int L = 0;
		if (nonvirus == 0)
			return L;

		Queue<int[]> Q = new LinkedList<>();
		for (int x : Pos) {
			Q.offer(V.get(x));
			m[V.get(x)[0]][V.get(x)[1]] = 1;
		}

		while (!Q.isEmpty() && nonvirus > 0) {
			int size = Q.size();
			L++;
			for (int i = 0; i < size; i++) {
				int P[] = Q.poll();
				for (int k = 0; k < 4; k++) {
					int nx = P[0] + dx[k];
					int ny = P[1] + dy[k];
					if (nx < 0 || ny < 0 || nx > m.length - 1 || ny > m[0].length - 1 || m[nx][ny] == 1)
						continue;
					if(m[nx][ny] == 0)
						nonvirus--;
					m[nx][ny] = 1;
					Q.offer(new int[] {nx,ny});
					
					if (nonvirus == 0)
						return L;
				}
			}
		}
		return nonvirus == 0 ? L : -1;
	}

 

 

코드

전체 코드는 다음과 같다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {
	int map[][];
	int nonvirus;
	int dx[] = { 0, 0, 1, -1 };
	int dy[] = { 1, -1, 0, 0 };

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

	public void solution() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());// matrix len
		int M = Integer.parseInt(st.nextToken());// virus
		nonvirus = 0;
		map = new int[N][N];
		ArrayList<int[]> virusLocate = new ArrayList<>();
		LinkedList<int[]> virusL = new LinkedList<>();

		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)
					virusLocate.add(new int[] { i, j });
				if (map[i][j] == 0)
					nonvirus++;
			}
		}
		int ans = -1;

		getVirusCombination(0, M, 0, virusLocate, virusL, new int[M], new boolean[virusLocate.size()]);
		while (!virusL.isEmpty()) {
			int[] P = virusL.pollFirst();
			int n = active_Virus(deep2Dcopy(map), P, virusLocate, nonvirus);
			if (ans == -1 && n > -1)
				ans = n;
			else if (ans > -1 && n > -1)
				ans = Math.min(ans, n);
		}
		System.out.println(ans);
	}

	public void getVirusCombination(int start, int M, int L, ArrayList<int[]> virusLocate, LinkedList<int[]> virusL,
			int[] arr, boolean[] visit) {
		if (L == M) {
			int a[] = IntStream.of(arr)
					.map(x->x)
					.toArray();
			virusL.add(a);
		}
		if (start == virusLocate.size() || L == M)
			return;
		for (int i = start; i < virusLocate.size(); i++) {
			if (!visit[i]) {
				arr[L] = i;
				visit[i] = true;
				getVirusCombination(i + 1, M, L + 1, virusLocate, virusL, arr, visit);
				visit[i] = false;
			}
		}
	}

	public int active_Virus(int m[][], int[] Pos, ArrayList<int[]> V, int nonvirus) {

		int L = 0;
		if (nonvirus == 0)
			return L;

		Queue<int[]> Q = new LinkedList<>();
		for (int x : Pos) {
			Q.offer(V.get(x));
			m[V.get(x)[0]][V.get(x)[1]] = 1;
		}

		while (!Q.isEmpty() && nonvirus > 0) {
			int size = Q.size();
			L++;
			for (int i = 0; i < size; i++) {
				int P[] = Q.poll();
				for (int k = 0; k < 4; k++) {
					int nx = P[0] + dx[k];
					int ny = P[1] + dy[k];
					if (nx < 0 || ny < 0 || nx > m.length - 1 || ny > m[0].length - 1 || m[nx][ny] == 1)
						continue;
					if(m[nx][ny] == 0)
						nonvirus--;
					m[nx][ny] = 1;
					Q.offer(new int[] {nx,ny});
					
					if (nonvirus == 0)
						return L;
				}
			}
		}
		return nonvirus == 0 ? L : -1;
	}

	public int[][] deep2Dcopy(int arr[][]) {
		int n = arr.length;
		int t[][] = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				t[i][j] = arr[i][j];
			}
		}
		return t;
	}

}