[백준/JAVA] 17142번: 연구소 3

📖 문제

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

 

 

 

💡  풀이 방식

• 조합 + BFS

[필요 자료구조]
- 바이러스 객체 ⇒ (행,열, 거리 값) 저장
- 인접한 4방향 탐색할 dx/dy 배열
- 바이러스 위치 저장용 객체 리스트
- 초기 빈 칸 개수 저장하는 int형 변수 zeroCnt

 

 

1. 연구소의 상태를 입력받는다.
   • 빈 칸(0)인 경우, zeroCnt에 +1 한다.
   • 바이러스(2)인 경우, 해당 위치와 0을 리스트에 저장한다.
2. 빈 칸의 갯수가 0이라면, 0을 출력하고 종료한다. / 그게 아니라면, 바이러스 위치 중 M개를 뽑아 바이러스를 심고 퍼뜨리는 데 걸리는 최소 시간을 계산한다.
   1. M개 바이러스 뽑기 > 조합 (백트래킹)
   2. 바이러스 퍼뜨리기 > BFS
      - M개 바이러스를 뽑았으면, 해당 위치들은 방문 처리하고, 큐에 추가한다.
      - [이동 X인 경우] 해당 칸에서 이동하려는 인접한 다음 칸이 1) 격자 범위를 벗어나거나, 2) 방문한 적 있거나, 3)벽인 경우
      - [이동 O인 경우] 이동하려는 칸이 빈 칸(0)이면, 방문하러 갈 거니까 빈 칸 개수를 줄인다.
          ▷ 빈 칸 갯수가 0이 된다면, 정답과 퍼뜨리는 데 걸린 시간+1 둘 중 더 작은 값으로 정답을 갱신한다.
          ▷ 그게 아니라면, 이동할 칸의 위치를 방문 처리하고, 시간은 +1해서 큐에 추가해 탐색한다.

 

 

 

💥 유의사항

- emptyCnt를 이용해 빈 칸의 갯수가 0이 되는 순가의 시간 초를 구하기

- 활성화된 바이러스가 퍼질 때, 비활성화된 바이러스도 지나갈 수 있다는 것을 잊지 말자,,,

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
 
    static int N,M;
    static int[][] lab;
 
    static List<Virus> vList = new ArrayList<>();
    static boolean[] chk;
 
    static int zeroCnt = 0; // 초기 빈 칸 개수
    static int answer = Integer.MAX_VALUE;
 
    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());
 
        lab = new int[N][N];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                lab[i][j] = Integer.parseInt(st.nextToken());
 
                if(lab[i][j] == 0)  // 빈 칸 개수 + 1
                    zeroCnt++;
                else if(lab[i][j] == 2)
                    vList.add(new Virus(i, j, 0));
            }
        }
 
        if(zeroCnt == 0) {  // 이 처리 안 하면 91%에서 틀림
            System.out.println(0);
            return;
        }
 
        chk = new boolean[vList.size()];
        dfs(0,0);
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }
 
    // M개 바이러스 선택하는 메소드 (조합)
    private static void dfs(int idx, int depth) {
        if(depth == M) {
            bfs(zeroCnt);
            return;
        }
 
        for(int i = idx ; i < vList.size() ; i++) {
            if(!chk[i]) {
                chk[i] = true;
                dfs(i + 1, depth + 1);
                chk[i] = false;
            }
        }
    }
 
    // 바이러스 퍼뜨리는 메소드 (BFS)
    private static void bfs(int emptyCnt) {
        Queue<Virus> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[N][N];
 
        for(int i = 0 ; i < chk.length ; i++) {
            if(chk[i]) {
                int x = vList.get(i).x;
                int y = vList.get(i).y;
                visited[x][y] = true;
                q.add(new Virus(x, y, 0));
            }
        }
 
        while(!q.isEmpty()) {
            Virus now = q.poll();
 
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];
 
                // [pass] 격자 범위 벗어나거나 / 방문한 적 있거나 / 벽인 경우
                if(nx < 0 || nx >= N || ny < 0 || ny >= N)  continue;
                if(visited[nx][ny] || lab[nx][ny] == 1) continue;
 
                if(lab[nx][ny] == 0) {  // 다음 칸이 빈 칸이면, 방문하러 갈 거니까 빈 칸 개수 줄이기
                    emptyCnt--;
                }
 
                if(emptyCnt == 0) { // 빈 칸 갯수가 0개면, 정답 갱신
                    answer = Math.min(answer, now.time + 1);
                    return;
                }
 
                // 다음 칸 방문 > 방문 처리하고, 시간 + 1해서 큐에 추가
                visited[nx][ny] = true;
                q.add(new Virus(nx, ny, now.time + 1));
            }
        }
    }
}
 
class Virus {
    int x,y,time;
 
    public Virus(int x, int y, int time) {
        this.x = x;
        this.y = y;
        this.time = time;
    }
}

 

 

 

 

➕ 다른 풀이 방식

- 내가 처음에 풀려고 했던 방식하고 비슷허다!!

[백준] 17142. 연구소 3 (Java, 자바)

 

---

💦 어려웠던 점

- 빈 칸의 수를 세서 문제 풀 때 활용할 생각을 하지 못 했다.

- 활성화되지 않은 바이러스 만났을 때 처리를 좀 어렵게 생각했던 것 같다.

 

 

🧐 새로 알게 된 내용

- 비활성화된 바이러스는 지나갈 순 있으나, 도착 순간에 시간을 갱신하면 안 되므로, 비활성화된 바이러스들 때문에 바이러스가 전부 퍼졌는지 확인하는 것은 빈 공간의 갯수로 파악하는 것이 훨씬 효과적이라고 한다...

- 조합 메소드 방식... 나는 방문 표시해서 원소를 뽑아쓰는 식으로 했는데, 다른 분들은 대개 크기가 M인 int형 배열에 원소를 넣고 뽑는 식으로 하셨다.

for (int i = idx ; i < vList.size(); i++) {
    arr[depth] = vList.get(i);
    dfs(i+1, depth+1);
}

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

백준 17142번. 연구소 3 (Java)