[Java] 백준 17141.연구소 2

➡️문제 링크

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

 

 

아이디어

문제를 보자마자 조합 + bfs가 생각났다. 야호~

 

 

문제 풀이

1. 2번 위치(바이러스 퍼뜨릴 수 있는 위치)를 M개 조합한다.

(이때, 2번 위치의 총개수보다 M개가 더 많을 경우, 현재 위치로 바이러스를 바로 확산한다.

즉, 조합 과정을 거치지 않음!)

2. 1번의 조합으로 바이러스를 퍼뜨린다.

3. 바이러스를 퍼뜨린 후, map을 전체 탐색하며 벽을 제외한 모든 영역에 바이러스가 확산됐는지 확인한다.

4. 3의 과정을 통과했을 경우, 1번에 최대시간값을 현재 최소 시간값과 비교하여 갱신한다.

 

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

public class Main {
	static int N, M;
	static int [][] map;
	static List<int []> point = new ArrayList<>();
	static int [] dx = {-1, 1, 0, 0};		// 상하좌우
	static int [] dy = {0, 0, -1, 1};
	static int minTime = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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];
		
		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) point.add(new int[] {i, j});		// 바이러스 퍼뜨릴 수 있는 위치
			}
		}
		
		if(point.size() <= M) {
			// 바로 바이러스 확산하기
			spread(point);
		}else {
			dfs(0, 0, new ArrayList<>());			
		}
		
		// 결과 출력
		if(minTime == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(minTime);
	}
	
	static void dfs(int start, int cnt, List<int []> curList) {
		if(cnt == M) {
			// M개 위치 선정
			spread(curList);		// 바이러스 확산
			return;
		}
		
		for(int i = start; i < point.size(); i++) {
			curList.add(point.get(i));
			dfs(i+1, cnt+1, curList);
			curList.remove(curList.size() - 1);
		}
	}
	
	static void spread(List<int []> list) {
		Queue<int []> que = new LinkedList<>();
		boolean [][] visited = new boolean[N][N];
		
		// 미리 방문처리하기
		for(int [] li : list) {
			que.add(new int[] {li[0], li[1], 0});
			visited[li[0]][li[1]] = true;
		}
		
		int result = -1;
		
		while(!que.isEmpty()) {
			int [] p = que.poll();
			result = Math.max(result,  p[2]);
			
			for(int i = 0; i < 4; i++) {
				int tx = p[0] + dx[i];
				int ty = p[1] + dy[i];
				
				if(!checkRange(tx, ty)) continue;	// 범위 밖 -> 다음차례
				if(visited[tx][ty]) continue;	// 이미 방문 경우 -> 다음 차례
				if(map[tx][ty] != 1 ) {
					
					visited[tx][ty] = true;
					que.add(new int[] {tx, ty, p[2]+1});
				}

			}
		}
		
		// 확인하기
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!visited[i][j] && map[i][j] != 1) return;	// 벽도 아닌데, 퍼지지 못 한 경우 -> 더이상 어떻게 할 수 없음
			}
		}
		
		minTime = Math.min(minTime, result);
	}
	
	static boolean checkRange(int x, int y) {
		return (x >= 0 && x < N && y >= 0 && y < N);
	}
}

 

 

 

구현 중 고민 사항

"바이러스는 상하좌우로 인접한 모든 빈칸으로 동시에 복제"

문제에서 "동시에"라는 키워드를 보고 "동시에"라면 순차가 아니라 한 번에 같이 퍼져야 하는데,

그걸 어떻게 하지?라는 생각이 들었다.

그리고 현재 조합에 들어가지 않은 2번의 위치는 어떻게 처리해야 하나 고민됐다.

처음에는 조합에서 첫 번째 위치만 que에 넣고 돌리려고 했다. 하지만 그렇게 된다면, 조합에 해당되는 2번 위치인지를 확인해줘야 하고, 남은 조합들은 어떻게 할 것인가라는 문제점이 발생했다.

그래서 다시 문제를 읽으니, "동시에"를 처음부터 que에 같이 넣고 방문 여부는 처음에 넣을 때부터 같이 처리하면 되겠다는 결론이 나왔다.

이렇게 하다 보니 "동시에" 문제와 "2번 위치" 문제를 한 번에 확인할 수 있었다

 

 

[추가사항]

문제에서 "2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다." 명시했지만,

확인하지 않고 풀어서 2의 개수가 M보다 같거나 작은 경우에는 바로 확산에 들어가도록 했다.

2의 개수가 M하고 같은 경우에는 바로 확산할 수 있어서 좋지만, 더 큰 경우에는 굳이 조건문 하나가

더 들어가는거니 빼면 좋을 것 같긴 하다

여러분은 어떻게 생각하시나요..?

 

 

[결과]

메모리: 47276KB

시간 : 268ms