백준저지 17142번 연구소 3 (Java)

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

17142번: 연구소 3

 

 

접근 방법

1. 연구소의 상태를 입력받으면서 바이러스의 위치를 리스트에 담는다.

2. 바이러스의 리스트 크기와 주어진 M을 통해 조합으로 M개의 바이러스를 구한다. 이때, 브루트포스 알고리즘으로 모든 경우를 생각한다.

3. BFS로 선택된 바이러스를 큐에 모두 담고 퍼뜨리기를 시작한다.

  3-1. 매번 큐의 사이즈를 구해 사이즈만큼 for문을 반복한다. 그 안에서 4방 탐색을 진행한다.

  3-2-1. 이때 방문 안 했고 0인 곳을 만나면 큐에 담고, 방문했다고 체크하고, 빈칸을 만났다고 true 체크한다.

  3-2-2. 만약 방문 안 했고 2인 곳을 만나면 비활성화 바이러스를 만난 것이기 때문에 큐에 담고, 방문했다고 체크한다.

  3-3. 빈칸을 만난 경우라면 cnt에 blank에 1까지 더한다. 빈칸을 아직 안 만났다면 blank만 1 더한다.

  3-4. 이 과정에서 cnt가 예전에 구했던 답이 될 min값보다 커지면 계속 구하는 것이 무의미하기 때문에 그만둔다.

  3-5. 다 끝나면 모든 빈칸에 바이러스가 방문했는지 체크한다. 만약 방문 안 한 빈칸이 있다면 바이러스가 모두 퍼진 것이 아니기 때문에 그냥 리턴한다.

  3-6. 그게 아니라면 제대로 된 것이기 때문에 cnt를 리턴하고, 2로 돌아가서 계속 반복한다.

 

 

 

생각

처음에 조합 코드를 짤 때 N과 M을 헷갈려서 시간을 잡아먹었다. 앞으로는 메소드를 짜면 제대로 이어지는지 확인을 해봐야겠다.

문제에서 '활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.'를 못 봤다. 문제를 좀 더 꼼꼼하게 읽어야겠다.

 

질문글(https://www.acmicpc.net/board/view/50436)에서 테스트케이스에 대한 설명을 통해 좀더 해결 방안을 생각해 볼 수 있었다. 나는 처음에는 큐 2개(활성 상태의 바이러스, 비활성 상태의 바이러스)를 사용하려 했다. 그런데 계속 답이 조금씩 틀리게 나왔다. 결국 블로그(https://mygumi.tistory.com/352)(https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/17142.java)의 도움을 통해 문제를 해결할 수 있었다..

 

 

 

 

 

코드

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

public class BOJ17142 {

    static int N, M, map[][], min, virusNum;
    static ArrayList<Virus> virusList; // 처음 입력될 때 모든 바이러스의 위치 저장
    static int[] selected; // 조합
    static Queue<Virus> q; // BFS
    static boolean[][] visited; // BFS
    static int[][] d = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

    static private class Virus { // 바이러스의 위치
        int x, y;

        public Virus(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        visited = new boolean[N][N];
        virusList = new ArrayList<>();
        q = new LinkedList<>();
        min = 2501; // 답 초기화. 연구소의 최대 크기가 50이라서 2501로 설정

        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) { // 입력받을 때 바이러스 위치 리스트에 담기
                    virusList.add(new Virus(i, j));
                }
            }
        }

        virusNum = virusList.size(); // 조합 위해 바이러스 전체 개수 저장
        selected = new int[M]; // 조합: M개의 바이러스 선택
        getMVirus(0, 0); // 조합하러 이동

        if (min == 2501) { // 다 했는데도 min값 변하지 않았다면 이동 불가능하기 때문에 -1
            bw.write(-1 + "\n");
        } else {
            bw.write(min + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void getMVirus(int cnt, int start) { // M개의 바이러스 선택 (조합)
        if (cnt == M) { // 다 선택되었다면
            min = Math.min(min, spreadVirus(selected)); // BFS하러 보냄
            return;
        }

        for (int i = start; i < virusNum; i++) {
            selected[cnt] = i;
            getMVirus(cnt + 1, i + 1);
        }
    }

    private static int spreadVirus(int[] selected) { // 선택된 바이러스를 가지고 퍼뜨리기 (BFS)
        for (int i = 0; i < N; i++) { // 매번 visited 배열을 false로 설정
            for (int j = 0; j < N; j++) {
                visited[i][j] = false;
            }
        }
        q.clear(); // 큐도 매번 비우기

        for (int i = 0; i < M; i++) { // 선택된 바이러스 위치를 true로 바꾸고 큐에 담기
            Virus vv = virusList.get(selected[i]);
            visited[vv.x][vv.y] = true;
            q.add(vv);
        }

        int cnt = 0; // 바이러스를 퍼뜨리는 시간
        int size = 0; // 큐 사이즈
        int blanks = 0; // 비활성화 바이러스 만난 시간
        while (!q.isEmpty()) {
            boolean countUp = false; // 비활성화 바이러스만 만났다고 우선 초기화

            if (cnt > min) { // cnt가 min보다 커지면 의미가 없기 때문에 리턴
                return 2501;
            }

            size = q.size(); // 현재 큐 사이즈 계산
            for (int j = 0; j < size; j++) { // 큐 사이즈만큼 반복
                Virus cur = q.poll();
                visited[cur.x][cur.y] = true;

                for (int i = 0; i < 4; i++) {
                    int dx = cur.x + d[i][0];
                    int dy = cur.y + d[i][1];
                    if (dx >= 0 && dx < N && dy >= 0 && dy < N && !visited[dx][dy]) {
                        if (map[dx][dy] == 0) { // 0이라면 바이러스가 퍼질 수 있다
                            visited[dx][dy] = true;
                            q.add(new Virus(dx, dy));
                            countUp = true; // 빈칸도 만났기 때문에 true
                        } else if (map[dx][dy] == 2) { // 2라면 비활성바이러스를 활성상태로 바꾼다
                            visited[dx][dy] = true;
                            q.add(new Virus(dx, dy));
                        }
                    }
                }
            }

            if (!countUp) { // 비활성화 바이러스만 만났다면
                blanks++;
            } else { // 빈칸도 만났다면
                cnt = cnt + blanks + 1;
                blanks = 0; // 초기화
            }
        }

        for (int i = 0; i < N; i++) { // 다 끝났는데도 방문 안했고 0인 곳이 있다면 바이러스가 다 안 퍼진 것
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && map[i][j] == 0) {
                    return 2501;
                }
            }
        }

        return cnt; // 여기까지 오면 여태까지 나온 값 중 최솟값이기 때문에 cnt 리턴
    }
}