[백준] 17141 연구소 2 - DFS(깊이우선탐색) + 조합(Combination) + BFS(너비우선탐색) JAVA

passionfruit200 2023. 11. 28. 10:32

2023. 11. 28. 10:32

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

17141번: 연구소 2

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러

www.acmicpc.net

코드설명

DFS(깊이우선탐색) + 조합(Combination) + BFS(너비우선탐색) 를 활용하는 문제입니다.

코드로직입니다.

입력 받기:
- 바이러스의 위치는 possibleVirus 리스트에 저장되며, 입력에서는 해당 위치를 2로 표시합니다.
- 초기에 바이러스가 없어야 하는 위치(벽 등)는 virusHaveToMoveCnt를 통해 카운트하고, 나중에 바이러스가 퍼지는데 필요한 시간을 계산할 때 사용합니다.
조합 구하기:
- getComb 함수를 통해 가능한 바이러스의 조합을 구합니다. 조합은 virusComb 배열에 저장됩니다.
바이러스 퍼뜨리기:
- virusWork 함수에서는 선택된 바이러스들을 시작으로 BFS(너비 우선 탐색)를 수행하여 바이러스를 확산시킵니다.
- visited 배열을 통해 방문한 위치를 기록하고, 바이러스가 있는 위치에서부터 상하좌우로 인접한 공간으로 바이러스를 확산시킵니다.
- 각 단계별로 시간을 측정하고, 모든 바이러스가 퍼진 경우에만 최소 시간을 갱신합니다.
결과 출력:
- 모든 바이러스를 퍼뜨리고 나면, 최소 시간인 answer를 출력합니다. 만약 모든 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력합니다.

모든 바이러스의 조합을 만들고, 각 조합에 대해 바이러스를 확산시키면서 최소 시간을 찾아내는 브루트 포스(완전 탐색) 를 사용하여 해결합니다.

조합을 구하는 방법은 여러가지 입니다.

1. M개만큼의 Size만큼만 구합니다. visited[M]으로 처리하는경우입니다. (즉, 3개의 바이러스 위치를 구한다고했을때 2 3 5 와 같이 바이러스 Index를 저장하는 방법입니다.)

2. 모든 바이러스의 개수 Size를 두고, 그 안에서 선택하느냐 안하느냐로 처리합니다.(즉, 5개의 바이러스에서 3개를 선택할경우 true true true false false 로 선택하는 경우입니다.)

속도와 메모리효율성은 1번이 높기에 1번으로 구현하는 것이 좋습니다.

가장 먼저 떠오르는 아이디어는 2번이 쉽게 떠오르기 쉽지만, M개의 바이러스를 선택한다는 개념으로 1번을 떠올리도록 하는 연습이 필요한 것 같습니다.

1번 방법을 떠올리기 어려운 이유중 하나는, 선택하지 않는 부분에 대한 정보를 가지고 있지 않기에 그런 것 같습니다.

그렇기에 바이러스의 위치를 처음에 모두 0 으로 만들어주고 시작하면, 가지고 있는 정보로만 처리할 수 있습니다.

추가로, 유의해야할점은

조합을 구할떄 자동으로 for문에서 i가 index를 기준으로 작동하므로, 굳이 visited를 처리할 필요가 없습니다.

    	for(int i=index; i<virusArr.size(); i++) {
//    		if(visited[i] == false) {
    			visited[i] = true;
    			combinationDFS(level + 1, i + 1, selected + 1);	
    			visited[i] = false;
//    		}
    	}

아래는 5개의 Virus가 있는 상황에서 3개의 조합을 선택하는, 즉, 5C3 = 10 의 코드입니다.

입력
7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

바이러스 조합
===============
 true true true false false
===============
 true true false true false
===============
 true true false false true
===============
 true false true true false
===============
 true false true false true
===============
 true false false true true
===============
 false true true true false
===============
 false true true false true
===============
 false true false true true
===============
 false false true true true

https://passionfruit200.tistory.com/845

[백준] 17142 연구소 3 - 조합 + 너비우선탐색(BFS) + 구현 JAVA

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가

passionfruit200.tistory.com

이전에 비슷한 문제인 연구소3은 위와 같이 possibleVirus 리스트를 활용하지않고, combVisited[][] 2차원 배열을 만들어서 사용할 바이러스의 위치를 true, false로 표시하여 진행했기에 바이러스의 경우마다 N^N의 맵을 모두 확인했어야했지만, 이 코드의 경우 해당 과정이 없어 더 속도가 빠릅니다.

또한 추가로 아래처럼 풀지않고, 직접 virusCnt와 virusHavetoMoveCnt가 같다면 Queue문을 종료시키며 time을 Return 시키는 방법도 좋아보입니다.

코드

조금 더 효율적인 코드입니다.

virus의 개수 M만큼만 선언하고, virus[level] 로 조합을 저장하여 사용하지 않는 바이러스들을 제외합니다.

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 {
	
	public static int N, M;
	public static int[][] arr;
	public static ArrayList<Integer> possibleVirus = new ArrayList<Integer>();
	public static int[] virusComb; 
	public static int virusIdx = 0, virusHaveToMoveCnt = 0;
	public static int answer = 51 * 51;
	public static boolean[][] visited;
	public static int[][] storeArr;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {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());
    	
    	arr = new int[N][N];
    	virusComb = new int[M];
    	virusHaveToMoveCnt = N * N - M;
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    			if(arr[i][j] == 2) {
    				possibleVirus.add( i * N + j);
    				arr[i][j] = 0;
    			}
    			if(arr[i][j] == 1) {
    				virusHaveToMoveCnt -= 1;
    			}
    		}
    	}
    	
    	
    	getComb(0, 0);
    	if(answer == 2601)
    		System.out.println(-1);
    	else 
    		System.out.println(answer - 1);
	}
	
	public static void getComb(int level, int idx) {
		if(level == M) {
			virusWork();
			return ;
		}
		for(int i=idx; i<possibleVirus.size();i++) {
			virusComb[level] = possibleVirus.get(i);
			getComb(level + 1, i + 1);
			
		}
	}
	
	public static void virusWork() {
		visited = new boolean[N][N];
		Queue<Node> q = new LinkedList<Node>();
		for(int i=0;i<M;i++) {
			q.offer(new Node(virusComb[i] / N, virusComb[i] % N));
			visited[virusComb[i] / N][virusComb[i] % N] = true;
		}

		int timeResult = 0;
		int qSize = q.size();
		int qCnt = 0;
		int virusCnt = 0;
		while(!q.isEmpty()) {
			Node temp = q.poll();
			qCnt += 1;
			for(int dir = 0; dir<4; dir++) {
				int nr = temp.r + dx[dir];
				int nc = temp.c + dy[dir];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
				if(visited[nr][nc] == true) continue; //이미 방문했다면, 
				if(arr[nr][nc] == 1) continue; //만약 벽이라면 이동불가합니다.
				
				virusCnt += 1;
				visited[nr][nc] = true;
				q.offer(new Node(nr, nc));
			}
			
			if(qCnt == qSize) {
				timeResult += 1;
				qSize = q.size();
				qCnt = 0;
			}
		}
		if(virusCnt == virusHaveToMoveCnt) { //모든 바이러스를 죽인경우 이므로 answer값과 갱신해봅니다.
			answer = Math.min(answer, timeResult);
		}
		
	}
}
class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r=r;
		this.c=c;
	}
}

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 {
	public static int N,M, K;
	public static int[][] map;
	public static int answer = 50*50 + 1;
	public static ArrayList<Node> virusArr = new ArrayList<Node>();
	public static boolean[] visited;
	public static int virusLocated = 99;
	public static int emptySize = 0;
    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];
    	emptySize = 0;
    	
    	int virusCanSize = 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) {
    				virusArr.add(new Node(i, j));
    				virusCanSize += 1;
    			}
    			if(map[i][j] == 0) {
    				emptySize += 1;
    			}
    		}
    	}
    	//전체 돌아야할 개수입니다.
    	emptySize += virusCanSize - M; 
    	
    	visited = new boolean[virusArr.size()];
    	combinationDFS(0, 0, 0);
    	if(answer == 50 * 50 + 1)
    		System.out.println("-1");
    	else 
    		System.out.println(answer);
    }
    
    public static void combinationDFS(int level, int index, int selected) {
    	if(selected == M) {
    		int[][] storeMap = new int[N][N];
    		for(int i=0;i<N;i++) {
    			for(int j=0;j<N;j++) {
    				storeMap[i][j] = map[i][j];
    			}
    		}
    		
    		System.out.println("===============");
    		for(int i=0;i<virusArr.size();i++) {
    			System.out.print(" "+visited[i]);
    			if(visited[i] == false) {
    				Node temp = virusArr.get(i);
    				map[temp.r][temp.c] = 0; 	
    			}
    		}
    		System.out.println();
    		
    		BFS();
    		for(int i=0;i<N;i++) {
    			for(int j=0;j<N;j++) {
    				map[i][j] = storeMap[i][j];
    			}
    		}
    		
    		return ;
    	}
    	if(index >= virusArr.size()) {
    		
    		return ;
    	}
    	
    	for(int i=index; i<virusArr.size(); i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
    			combinationDFS(level + 1, i + 1, selected + 1);	
    			visited[i] = false;
    		}
    	}
    	
    }
    
    public static void BFS() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0, 0, -1, 1};
    	Queue<Node> q = new LinkedList<>();
    	
    	for(int i=0;i<virusArr.size();i++) {
    		if(visited[i] == true) {
    			Node temp = virusArr.get(i);
    			q.offer(new Node(temp.r, temp.c));		
    		}
    	}
    	
    	int qSize = q.size();
    	int qCnt = 0;
    	int time = 0;
    	int virusMoveCnt = 0;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		
    		qCnt += 1;
    		for(int dir = 0; dir < 4; dir++) {
    			int nr = temp.r + dx[dir];
    			int nc = temp.c + dy[dir];
    			
    			if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
    			//벽이거나 이미 바이러스가 존재한다면 멈춰도 됩니다.
    			if(map[nr][nc] == 1 || map[nr][nc] == 2) continue;
    			virusMoveCnt += 1;
    			map[nr][nc] = 2;
    			q.offer(new Node(nr, nc));
    		}
    		
    		if(qSize == qCnt) {
    			qSize = q.size();
    			qCnt = 0;
    			time += 1;
    		}
    	}
    	
    	if(virusMoveCnt == emptySize) {
//    		System.out.println();
//        	System.out.println("TIME:"+time);
        	answer = Math.min(answer, time - 1);
    	}
    	
    }
    
}

class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 18808 스티커 붙이기 - 구현(implementation) + 시뮬레이션(Simulation) JAVA (0)	2023.11.30
[백준] 17281 ⚾ - DFS(깊이우선탐색) + 일반 순열(Normal Permutation) + 구현 JAVA (0)	2023.11.28
[백준] 1405 미친 로봇 - 완전탐색(BruteForce) + DFS(깊이우선탐색) + 확률론(Probability) JAVA (0)	2023.11.27
[백준] 27172 수 나누기 게임 - 에라토스테네스의 체 JAVA (0)	2023.11.27
[백준] 17090 미로 탈출하기 - DFS(깊이우선탐색) + DP(Dynamic Programming) JAVA (0)	2023.11.27

passionfruit200