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

passionfruit200 2023. 11. 9. 23:16

2023. 11. 9. 23:16

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

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고,

www.acmicpc.net

코드설명

1. 연구소의 초기 상태를 나타내는 2차원 배열(map)을 입력받으며, 동시에 빈 칸의 개수(zeroCnt)를 세어둡니다.
2. 조합 구하여 비활성화 바이러스(값이 2) 중에서 M개를 놓을 수 있는 모든 조합을 구합니다. 이때, 조합은 combVisited 배열을 사용합니다.
3. BFS 탐색: 각 조합에 대해 BFS 탐색을 수행합니다. BFS는 큐를 이용하여 바이러스를 퍼뜨리는 과정을 구현합니다.

3-1 먼저, 선택된 활성화 바이러스의 위치를 큐에 넣고 해당 위치를 방문 처리합니다.
3-2 큐가 빌 때까지 아래 과정을 반복합니다.
3-2-1. 큐에서 하나의 위치를 꺼내고, 상하좌우로 인접한 빈 칸을 찾아 큐에 넣고 방문 처리합니다.
3-2-2. 이때, 바이러스가 퍼지면서 빈 칸의 개수를 세어가며(zeroCnt) 모든 빈 칸이 감염되면 최소 시간을 갱신하고 종료합니다.

문제에서 실수했었던 부분은,

첫번쨰, 만약 모든 0 을 모두 지웠다면 바로 종료시켜야만 합니다. (즉 빈칸을 모두 지웠다면 종료하면 됩니다.)

바로 종료시키지 않을 경우, 연결된 바이러스까지 넘어가며 q에 time이 게속 쌓여서 최소의 바이러스가 종료되었때의 시간을 구하지 못합니다.

if(zeroCnt == cnt) {
    answer = Math.min(answer,  temp.time + 1);
    return ;
}

위의 코드를 아래의 코드처럼 만약 해당 Queue에서 모든 바이러스의 확산이 종료되었다면 바로 종료시키게 두어 다른 활성화 바이러스로 넘어가서 불필요한 time이 늘어나는것을 방지해야 합니다.

그 과정에서 만약 map[][이 빈칸일 경우에만, 빈칸을 바이러스로 바꾸어주었다는 로직을 추가해주어야합니다.

초기에 비활성화된 바이러스는 세지 않았기 떄문입니다.

if(map[nr][nc] == 0) {
    moveCnt += 1;
}

또한, while문 안이 아닌 while문 안 속의 for문에 종료조건을 넣는 이유는 아직 남아있는 dir이 돌면서 cnt값이 계속해서 올라갈 수 있어 올바르게 갱신시키지 못할 수 있습니다.

while(!q.isEmpty()) {
    Node temp = q.poll();

    if(zeroCnt == cnt) { //만약 여기에서만 종료처리를 한다면 올바르게 계산되지 않는다.
        timeCnt = temp.time;
        break;
    }


    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) continue; //벽이라면 통과못해요.
        if(visited[nr][nc] == true) continue; //이미 지나간곳은 못지나가요.

        visited[nr][nc] = true; //방문처리합니다.
        if(map[nr][nc] == 0) {
            cnt += 1; //진짜로 0 일경우에만 1을 더해가며 빈 칸을 하나씩 채워나가며 개수를 세어나갑니다.
        }
        if(zeroCnt == cnt) {
            answer = Math.min(answer,  temp.time + 1);
            return ;
        }
//				System.out.println("tempR:"+nr+"tempC:"+nc+"tempCnt:"+(temp.time + 1)+ "cnt:"+cnt);
        q.offer(new Node(nr, nc, temp.time + 1)); //
    }
}

혹은 마지막 0 에 바이러스를 갱신하였을떄의 시간을 temp.time + 1 로 갱신하는 방법도 존재합니다.

세번쨰, 유의사항으로는 qSize와 qCnt를 활용하여 직접 바이러스가 이동한 초를 계산하였는데, BFS에서 단순히 time 데이터를 return 해주면 해당 값은 선입선출이므로 해당 시간대가 최소시간대입니다.

네번쨰는, 어떤 문제를 풀떄 문제 조건에 맞게 유연하게 생각해야한다고 느꼈습니다.

이 문제같은경우 바이러스를 만나면 비활성화 상태에서 활성화 상태로 변하는 특징이 있었습니다. 그렇기에 map[][]에 바이러스를 지우지 않고, 그대로 냅두면서 조합을 활용하여 활성화 바이러스를 선택했어야했는데, 모두 0 으로 바꾼뒤 선택한 바이러스만 2 로 바꾸는 작업을 통해서 로직이 매우 복잡해졌었습니다.

그렇기에 문제에 알맞는 아이디어를 떠올려야만 합니다.

여섯번쨰는, zeroCnt == 0 일경우, (M이 0 인경우), 바이러스가 없으므로 무조건 답은 0 입니다.

코드

깔끔하게 정리해본 코드입니다.

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[][] map;
	public static int[] selected;
	public static int MAX_VALUE = 2500;
	public static int zeroCnt = 0, answer = MAX_VALUE;
	public static ArrayList<Node> virusArr = new ArrayList<Node>();
    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];
    	selected = new int[M];
    	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, 0));
    			}
    			if(map[i][j] == 0) {
    				zeroCnt += 1;
    			}
    		}
    	}
    	if(zeroCnt == 0) {
    		System.out.println(0);
    		return ;
    	}
    	simulate(0, 0);
    	if(answer == MAX_VALUE) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer + 1);
    	}
    }
    
    public static void simulate(int level, int idx) {
    	if(level == M) {
    		answer = Math.min(answer, BFS());
    		return ;
    	}
    	for(int i=idx; i<virusArr.size();i++) {
    		selected[level] = i;
    		simulate(level + 1, i + 1);
    		selected[level] = -1;
    	}
    	
    }
    
    public static int BFS() {
    	boolean[][] visited = new boolean[N][N];
    	Queue<Node> q = new LinkedList<>();
    	int moveCnt = 0;
    	for(int i=0;i<M;i++) {
    		q.offer(new Node(virusArr.get(selected[i]).r, virusArr.get(selected[i]).c, 0));
    		visited[virusArr.get(selected[i]).r][virusArr.get(selected[i]).c] = true;
    	}
    	int[] dx = {-1, 1, 0, 0};
    	int[] dy = {0, 0, -1, 1};
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		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(map[nr][nc] == 1) continue;
    			if(map[nr][nc] == 0) {
    				moveCnt += 1;
    			}
    			if(moveCnt == zeroCnt) {
    				return temp.time;
    			}
    			visited[nr][nc] = true;
    			q.offer(new Node(nr, nc, temp.time + 1));
    		}
    	}
    	return MAX_VALUE;
    }
    
}
class Node{
	int r;
	int c;
	int time;
	public Node(int r, int c, int time) {
		this.r=r;
		this.c=c;
		this.time = time;
	}
}

바로 종료시켜서 처리한코드.

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[][] map;
	public static int[][] copyMap;
	public static boolean[][] combVisited;
	public static boolean[][] visited;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int zeroCnt = 0;
	public static int answer = Integer.MAX_VALUE;
	public static StringBuilder sb = new StringBuilder();
	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];
    	combVisited = new boolean[N][N];
    	
    	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] == 0) {
    				zeroCnt += 1;
    			}
    		}
    	}
    	
//    	System.out.println("zeroCnt:"+zeroCnt);
    	if(zeroCnt == 0) {
    		System.out.println("0");
    		return ;
    	}
    	getComb(0, 0);	
    	if(answer == Integer.MAX_VALUE) {
    		System.out.println("-1");
    		return ;
    	}
    	System.out.println(answer);
	}
	
	public static void getComb(int level, int idx) {
		if(level == M) {
			BFS();
			return ;
		}
		
		for(int i=idx;i<N*N;i++) {
			if(map[i/N][i%N] == 2) { //만약 비활성화 바이러스인경우에만 활성화 바이러스의 조합에 들어갑니다.
				combVisited[i/N][i%N] = true;
				getComb(level + 1, i + 1);
				combVisited[i/N][i%N] = false;				
			}

		}
		
	}
	
	public static void BFS() {
		
		Queue<Node> q = new LinkedList<>();
		visited = new boolean[N][N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(combVisited[i][j] == true) {
					q.offer(new Node(i, j, 0));
					visited[i][j] = true;
				}
			}
		}
		
		int cnt = 0;
		int timeCnt = 0; //시간을 하나씩 세어갑니다.
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			if(zeroCnt == cnt) {
				timeCnt = temp.time;
				break;
			}
			
			
			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) continue; //벽이라면 통과못해요.
				if(visited[nr][nc] == true) continue; //이미 지나간곳은 못지나가요.
				
				visited[nr][nc] = true; //방문처리합니다.
				if(map[nr][nc] == 0) {
					cnt += 1; //진짜로 0 일경우에만 1을 더해가며 빈 칸을 하나씩 채워나가며 개수를 세어나갑니다.
				}
				if(zeroCnt == cnt) {
					answer = Math.min(answer,  temp.time + 1);
					return ;
				}
//				System.out.println("tempR:"+nr+"tempC:"+nc+"tempCnt:"+(temp.time + 1)+ "cnt:"+cnt);
				q.offer(new Node(nr, nc, temp.time + 1)); //
			}
		}
		
	}
	
	
}
class Node{
	int r;
	int c;
	int time;
	public Node(int r, int c, int time) {
		this.r=r;
		this.c=c;
		this.time = time;
	}
}

0 을 만날때마다 시간을 갱신합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int N, M;
	public static int[][] map;
	public static int[][] copyMap;
	public static boolean[][] combVisited;
	public static boolean[][] visited;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int zeroCnt = 0;
	public static int answer = Integer.MAX_VALUE;
	public static StringBuilder sb = new StringBuilder();
	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];
    	combVisited = new boolean[N][N];
    	
    	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] == 0) {
    				zeroCnt += 1;
    			}
    		}
    	}
    	
    	if(zeroCnt == 0) {
    		System.out.println("0");
    		return ;
    	}
    	getComb(0, 0);	
    	if(answer == Integer.MAX_VALUE) {
    		System.out.println("-1");
    		return ;
    	}
    	System.out.println(answer);
	}
	
	public static void getComb(int level, int idx) {
		if(level == M) {
			BFS();
			return ;
		}
		
		for(int i=idx;i<N*N;i++) {
			if(map[i/N][i%N] == 2) { //만약 비활성화 바이러스인경우에만 활성화 바이러스의 조합에 들어갑니다.
				combVisited[i/N][i%N] = true;
				getComb(level + 1, i + 1);
				combVisited[i/N][i%N] = false;				
			}

		}
		
	}
	
	public static void BFS() {
		
		Queue<Node> q = new LinkedList<>();
		visited = new boolean[N][N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(combVisited[i][j] == true) {
					q.offer(new Node(i, j, 0));
					visited[i][j] = true;
				}
			}
		}
		
		int cnt = 0;
		int timeCnt = 0; //시간을 하나씩 세어갑니다.
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			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) continue; //벽이라면 통과못해요.
				if(visited[nr][nc] == true) continue; //이미 지나간곳은 못지나가요.
				
				
				if(map[nr][nc] == 0) {
					cnt += 1; //진짜로 0 일경우에만 1을 더해가며 빈 칸을 하나씩 채워나가며 개수를 세어나갑니다.
					timeCnt = temp.time + 1; //0일경우 이전시간 + 1 처리하여 시간처리가 원활하다.
				}
				visited[nr][nc] = true; //방문처리합니다.
				q.offer(new Node(nr, nc, temp.time + 1)); //
			}
		}
		
		if(zeroCnt == cnt) {
			answer = Math.min(answer,timeCnt);
			return ;
		}
		
	}
	
	
}
class Node{
	int r;
	int c;
	int time;
	public Node(int r, int c, int time) {
		this.r=r;
		this.c=c;
		this.time = time;
	}
}

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

[백준] 2146 다리 만들기 - BFS(너비우선탐색) JAVA (0)	2023.11.11
[백준] 1726 로봇 - 너비우선탐색(BFS) JAVA (0)	2023.11.10
[백준] 17135 캐슬 디펜스 - 깊이우선탐색(DFS) + 조합(Combination) + 너비우선탐색(BFS) JAVA (0)	2023.11.09
[백준] 1941 소문난 칠공주 - 조합(Combination) + BFS(너비우선탐색) JAVA (0)	2023.11.09
[백준] 1516 게임 개발 - DP + 위상 정렬(Topology Sort) JAVA (0)	2023.11.09

passionfruit200