문제 링크
문제 풀이
저번에 연구소1을 풀어서 그런지 접근 자체는 쉽게 할 수 있었다. 어느 자리에 바리어스들을 뿌릴지를 dfs를 통해서 자리를 정했고, 정한 자리를 토대로 bfs를 돌려서 문제를 풀었다. 연구소2는 어디가고 연구소3부터 풀게되었다. 그래서 연구소3을 다풀고 연구소2도 풀어보았다.
맵을 원본맵과, 막 케이스마다 사용하는 맵으로 나누기 위해서 map과 originMap을 선언했다. map들을 bfs가 시작할때 originMap의 값들을 deepCopy한다.
map의 값이 0인경우는 zerocnt를 증가시켰다. zerocnt 총 몇개의 빈칸을 전염시켜야 하는지를 파악하기 위해서 사용했다.
map의 값이 2인경우에는 활성 virus를 놓을 자리이므로 따로 dfs를 사용하기 위해서 list에 저장해 놓았다.dfs 들어가기전에 zerocnt 가 0인경우는 dfs를 시작할 필요가 없으므로 조건문을 사용하여 경우를 나눠서 처리했다.
originMap = new int[n][n]; int [][] map = new int[n][n]; List<Node> viruspos = new ArrayList<>(); for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ map[i][j] = sc.nextInt(); originMap[i][j] = map[i][j]; if(map[i][j]==2){ viruspos.add(new Node(i,j)); }else if(map[i][j]==0){ zerocnt++; } } }
dfs부분은 간단했다. dfs의 idx가 m(활성바이러스의 수)가 될때 return 시켰으며
중복을 피하기 위해서 for문에서 사용할 변수 checker를 사용했다.
ex) 1 2 3 이 나오면 1 3 2 는 나올 필요가 없디 때문이다. 기본 dfs틀을 사용해서 풀었고 idx == m 인 경우에 bfs를 돌려서 결과를 얻도록 구현했다.public static void dfs(int idx,int checker, List<Node>viruspos,Node [] pos, int [][]map){ if(idx==m){ //bfs돌리기 bfs(pos,map); // -1 이 나온 상태에서 res값이 갱신되지 않았다는것은, 모든 칸에 바이러스를 퍼트리는 경우가 나오지 않았다는 뜻이므로 //minuschk라는 값을 true로 바꿔둬서 마지막에 -1을 사용할지 res값을 사용할지 체크한다. if(temper == -1){ if(res==Integer.MAX_VALUE){ minuschk = true; } }else{ //만약에 res값이 -1이 아닌 값으로 바꼈다면, minuschk를 false로바꿔서 마지막에 res가 -1로 되는 것을 막는다. res = Math.min(res,temper); minuschk = false; } //temper값 초기화... temper=0; return; } for(int i=checker; i<viruspos.size(); i++){ if(viruschk[i]){ continue; } pos[idx] = viruspos.get(i); viruschk[i] = true; dfs(idx+1,i,viruspos,pos,map); viruschk[i] = false; } }
bfs부분도 기본적인 bfs틀을 사용했지만 몇가지 차이가 있었다.
우선 queue를 두개를 사용했다. 내가 생각한 로직으로는 1초에 확산된 바이러스를 다시 queue에 넣게되면, 시간 구분을 할 수 없게 되는 문제가 생길것이라고 판단했고
해당 시간동안 확산된 바이러스들을 따로 담을 queue를 만들어서 해당 시간동안 확산된 바이러스들을 temp에 담고 -> 이것을 다시 queue로 옮겨서 while문을 돌렸다.
그래서 바이러스가 확산이 되는 경우 timer를 true로 바꿨고 이 경우에 시간을 나타내기 위해 사용한 temper의 값을 1증가 시켰다.
여기서 cnt = zerocnt 인데, cnt가 0이 되는경우 아무리 queue에 바이러스가 남아있더라도 돌 필요가 없기 때문에 바로 break를 해주었다.
여기서 cnt가 0이 아닌데 bfs가 끝나게 되는 경우는 -1로 바꿔주었다.
bfs가 끝나고 최소 시간을 구하기 위해서 temper와 res를 사용했는데 res는 출력값이고, temper는 bfs를 돌면서 구해지는 각 케이스마다의 최소 시간이다. 모든 케이스가 끝나기전에 temper가 -1이 되면 어떤 값이 오던지 -1이 되버리므로 -1이 되는 경우는 기억을 해뒀다가. 모든 케이스가 끝났을때도 minuschk값이 true로 남아있다면 결과적으로 -1을 아닌경우에는 최솟값을 출력하도록 했다.
if(temper == -1){ if(res==Integer.MAX_VALUE){ minuschk = true; } }else{ //만약에 res값이 -1이 아닌 값으로 바꼈다면, minuschk를 false로바꿔서 마지막에 res가 -1로 되는 것을 막는다. res = Math.min(res,temper); minuschk = false; } //temper값 초기화... temper=0; return;dfs(0,0,viruspos,pos,map); System.out.println(minuschk ? -1 : res);
코드
import java.util.*;
public class Main {
static int n;
static int m;
static boolean [] viruschk;
static int res = Integer.MAX_VALUE;
static int temper =0;
static boolean minuschk = false;
static int zerocnt = 0;
//상 우 하 좌
static int [] diry = {-1,0,1,0};
static int [] dirx = {0,1,0,-1};
static int [][] originMap; //맵 원본
public static class Node{
int y;
int x;
public Node(int y, int x){
this.y=y;
this.x=x;
}
public String toString(){
return "y : "+y+" x : "+x;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt(); //바이러스를 놓을수 있는 위차
originMap = new int[n][n];
int [][] map = new int[n][n];
List<Node> viruspos = new ArrayList<>();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = sc.nextInt();
originMap[i][j] = map[i][j];
if(map[i][j]==2){
viruspos.add(new Node(i,j));
}else if(map[i][j]==0){
zerocnt++;
}
}
}
Node [] pos = new Node[m];
viruschk = new boolean[viruspos.size()];
//위치 설정
if(zerocnt==0){
System.out.println(0);
}else{
dfs(0,0,viruspos,pos,map);
System.out.println(minuschk ? -1 : res);
}
}
public static void dfs(int idx,int checker, List<Node>viruspos,Node [] pos, int [][]map){
if(idx==m){
//bfs돌리기
bfs(pos,map);
// -1 이 나온 상태에서 res값이 갱신되지 않았다는것은, 모든 칸에 바이러스를 퍼트리는 경우가 나오지 않았다는 뜻이므로
//minuschk라는 값을 true로 바꿔둬서 마지막에 -1을 사용할지 res값을 사용할지 체크한다.
if(temper == -1){
if(res==Integer.MAX_VALUE){
minuschk = true;
}
}else{
//만약에 res값이 -1이 아닌 값으로 바꼈다면, minuschk를 false로바꿔서 마지막에 res가 -1로 되는 것을 막는다.
res = Math.min(res,temper);
minuschk = false;
}
//temper값 초기화...
temper=0;
return;
}
for(int i=checker; i<viruspos.size(); i++){
if(viruschk[i]){
continue;
}
pos[idx] = viruspos.get(i);
viruschk[i] = true;
dfs(idx+1,i,viruspos,pos,map);
viruschk[i] = false;
}
}
public static void bfs(Node [] pos, int [][]map){
Queue<Node> queue = new LinkedList<>(); //temp 에서 모인 바이러스들을 확신시키는 로직 수
Queue<Node> temp = new LinkedList<>(); //해당 초동안에 확산된 바이러스들을 담음
int cnt = zerocnt;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = originMap[i][j];
}
}
for(int i=0; i<pos.length; i++){
int now_y = pos[i].y;
int now_x = pos[i].x;
map[now_y][now_x]=3; //진짜 바이러스
temp.add(new Node(now_y,now_x));
}
while(!temp.isEmpty()) {
while(!temp.isEmpty()){
queue.add(temp.poll());
}
boolean timer = false; //이번 초동안에 확산시킨 바이러스가 있다면 ++를 해준다.
while (!queue.isEmpty()) {
Node now = queue.poll();
for (int i = 0; i < 4; i++) {
int now_y = now.y + diry[i];
int now_x = now.x + dirx[i];
if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < n) {
if (map[now_y][now_x] == 0 || map[now_y][now_x] == 2) {
if(map[now_y][now_x]==0){
cnt--;
}
map[now_y][now_x] = 3;
timer = true;
temp.add(new Node(now_y, now_x));
}
}
}
}//queue.isEmpty()
if(timer){
temper++;
}
if(cnt==0){
break;
}
}//temp.isEmpty()
//체크
temper = cnt !=0 ? -1 : temper;
}
}
