[JAVA][백준 17142] 연구소 3
- 알고리즘
- 2021. 4. 2.
SHORTCUT
| 사이트명 | 백준 |
| 문제 링크 | www.acmicpc.net/problem/17142 |
| 주요 알고리즘 | 조합, BFS |
| 사용 언어 | Java 자바 |
| 알고리즘이 낯선 사람들을 위해 생각 노트를 같이 두었습니다. | |
1. 문제
2. 입력 / 출력
🧶 Check Point
- 풀이 알고리즘의 결정
1. 바이러스 개수는 최대 10개 = 10C5 조합 결과 250개
2. 최대 칸 수 50칸 = 50^2 그래프 탐색시 최대 걸리는 시간 2500
===> 완전 탐색으로 가능
- 출력 값
출력이 결국 모든 칸에 바이러스가 있게 되는 최소 시간. 따라서 칸과 시간을 중점으로 체크해야 한다.
3. 풀이
3-1. 생각 노트
1. 바이러스(2)인 수를 전부 virusList에 넣기
2. nCm 의 형식으로 모든 경우에 대한 조합 생성
3. 조합을 기준으로 virusList에서 get(i)로 해당 값을 Queue에 넣고 실행
이 때, 중요한 포인트는
1. 시간이 증가되는 것처럼 동시에 진행된다? BFS
- 경로 찾기, 다양한 경우가 중요하면 DFS
2. BFS에서 Queue에 삽입한다? 거기도 방문 체크를 하자!
- 이거 까먹기 쉽다..
3-2. 변수명
| 변수명 | 설명 |
|
static ArrayList<Virus> virusList |
바이러스들의 위치와 시간값을 기록하기 위한 리스트. 이 리스트는 맨 처음 입력받은 대로 고정이고 조합 결과에 따라 인덱스로 접근할 수 있게 해줌. |
|
다른 변수들은 코드에 적어두었습니다. |
|
3-3. 코드 보기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
/* 풀이 생각
* 1. 바이러스(2)인 수를 전부 virusList에 넣기
* 2. nCm 의 형식으로 모든 경우에 대한 시간 계산
* 3. m번 반복하며 BFS로 바이러스 확산 처리
*/
// 바이러스의 시간과 위치를 기록하기 위한 객체
class Virus {
int x;
int y;
int time;
public Virus(int x, int y, int level) {
this.x = x;
this.y = y;
this.time = level;
}
}
public class Main {
static int N, M;
static int[] picked; // 뽑은 조합을 기록
static ArrayList<Virus> virusList = new ArrayList<>();
static int[][] map;
static boolean[][] isVisit;
static int blank; // 빈칸 기록
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]); // 연구소 크기
M = Integer.parseInt(input[1]); // 바이러스 개수
map = new int[N][N];
// ==============
// * 데이터 입력
// ==============
for (int i = 0; i < N; i++) {
input = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
int num = Integer.parseInt(input[j]);
map[i][j] = num;
if(num == 2) {
virusList.add(new Virus(i,j,1));
}else if(num == 0) {
blank++; // 비어있는 칸(바이러스가 퍼져야 할)의 갯수
}
}
}
// 빈칸 없는 경우 바로 끝
if(blank == 0) {
System.out.println(0);
return;
}
// 뽑은 조합을 저장하기 위한 배열
picked = new int[M];
// 조합 + 탐색 시작
combination(0, 0);
// 다 못채우면 그냥 끝냄 ->
if(min == Integer.MAX_VALUE) {
System.out.println(-1);
return;
}
System.out.println(min);
}
// cnt(현재까지 뽑은 수), cur(현재 가르키는 번호)
private static void combination(int cnt, int cur) {
if(cnt == M) {
BFS(); //조합이 완성되면 탐색 시작
return;
}
for (int i = cur; i < virusList.size(); i++) {
picked[cnt] = i;
combination(cnt+1, i+1);
}
}
private static void BFS() {
Queue<Virus> q = new LinkedList<>();
isVisit = new boolean[N][N];
// 뽑힌 수대로 바이러스 리스트에 접근해서 Q에 삽입
for (int i = 0; i < M; i++) {
q.add(virusList.get(picked[i]));
isVisit[virusList.get(picked[i]).x][virusList.get(picked[i]).y] = true;
}
int time = 0; // 걸린 시간 기록
int count = 0; // 빈칸 확산 카운팅
while(!q.isEmpty()) {
Virus v = q.poll();
for (int k = 0; k < 4; k++) {
int nx = v.x + dx[k];
int ny = v.y + dy[k];
// 이전에 있던 바이러스의 시간값을 받아오므로 계속 증가할 수 밖에 없음
time = v.time;
// 범위 밖 OR 이미 방문 = 아웃
if(!(0 <= nx && nx < N && 0 <= ny && ny < N) || isVisit[nx][ny]) continue;
// 빈칸이어서 확산한 경우)
if(map[nx][ny] == 0) {
isVisit[nx][ny] = true;
count++;
q.add(new Virus(nx,ny,v.time+1));
}
// 확산은 못하지만 지나갈 수 있는 경우)
if(map[nx][ny] == 2) {
isVisit[nx][ny] = true;
q.add(new Virus(nx,ny,v.time+1));
}
}
// 만약 이미 빈칸이 채워졌다면 사전에 종료시킴으로써 시간값의 계속 증가를 방지
if(count == blank) {
time++; // 이경우, 새로 뽑은 시간값 할당이 안되므로, 임의로 1 증가
break;
}
};
if(count != blank) return; // 다 못채우면 그냥 끝내기
// time-1의 이유 : 마지막에 +1한 상태를 q에 날리기 때문
min = Math.min(min, time-1);
}
}
3-4. 마무리
틀린 이유
1. 각 바이러스마다 시간 값을 기록하고 이를 지도에 반영했다.
- 머릿속으로 '각 바이러스마다 Queue로 접근하며 확산할텐데, 그럼 그 때의 시간을 어떻게 기록하지?' 에 대한 고민의 결과였다..
- 저것을 기록하기 위해 copyMap을 만들고, deep copy를 해서 직접 배열 내의 값을 time으로 할당하는 작업을 가졌다. (활용도 안하면서)
- 왜 계속 실제 map을 바꿔야 한다고 생각했을까? 방문 배열만 활용해서 방문한 것 처럼 처리가 되는데
2. 비활성 바이러스더라도 지나갈 순 있다.
- 비활성 바이러스에 대한 처리를 아예 하지 않았다. 생각을 못한거다..
이건 조합을 활용한 BFS 문제다. 따라서 조합에 대한 코드를 빠삭히 알고 있어야 한다.
또 실제 지도를 업데이트 해야 한다는 생각때문에 코드를 복잡하게 구성했다. 예시에 나온 것 처럼 실제 맵을 업데이트 할 필요 없이, 방문 배열만 확인하면 된다. 그래서 비어있는 칸을 blank로 입력 받아서 이를 확인하는 작업을 수행하면 된다.
사실 더 쉽게 짤 수 있을 것 같은데, 일단 내가 틀렸던 부분 위주로 수정해서 업로드했다.
다양한 반례에 대해 생각하자.