백준 17142번 : 연구소 3 풀이 [Java]

서론

위 문제를 풀기 전에 아래 두 문제를 풀어보길 권장한다!

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

14502번: 연구소

17141번: 연구소 2

 

풀이

전형적인 조합 + BFS의 구현 문제지만 문제 내용을 이해하기 어려워서 오래 걸렸다. 문제의 요점은 N * N의 연구소에서 비활성화된 바이러스들 중 M개를 골라서 활성화 상태로 변경해야 한다. 결론적으로 BFS를 통해 모든 벽이 아닌 칸을 바이러스로 만들 수 있는 최솟값을 찾는게 이 문제의 핵심이다.

 

이 문제를 해결하기 위해서 다음을 고려해보자!

 

원래 바이러스가 있는 칸은 BFS를 통해서 도달하건 말건 바이러스가 있는 칸이다.

첫번째로 원래 비활성 바이러스가 있는 칸은 BFS를 통해 도달하지 않아도 바이러스가 있는 칸으로 따진다. 다음 예시를 보면서 이해해보자.

4 1
2 1 1 2
1 1 1 1
1 1 1 1
1 1 1 1

output : 0

위의 예시에서 고를 수 있는 조합의 개수는 총 두 가지이다. ((0, 0) 과 (0, 3)) 이때 각 위치에서 BFS를 시작한다면 1이 벽이므로 더 이상 진행할 수 없다는 사실을 알 수 있다. 따라서 출력값은 -1이 나와야한다고 생각할 수 있는데, 각 위치에는 이미 비활성화된 바이러스가 존재한다. 따라서 위의 경우에는 출력값이 0이 나와야 정답이다 .

 

 

그러면 원래 바이러스가 있는 칸은 안가도 되지 않나요?

다음과 같은 예시라면 빈칸에 도달하기 위해서는 무조건 원래 바이러스가 있는 칸도 가야한다.

5 1
2 2 0 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 0 1 1

output : 4

만약 원래 바이러스가 있는 칸은 안간다고 코드를 작성하면 위와 같은 경우에는 빈칸인 0에 도달하지 못할 것이다. 따라서 원래 바이러스 유무와 상관 없이 칸에 도달할 수 있어야한다.

 

따라서 위와 같은 경우를 생각해서 코드를 작성한다면, 세가지 boolean 2차원 배열을 만들어서 하나는 원래 바이러스가 있는 위치를 관리하고(virus), 하나는 모든 빈칸에 바이러스가 채워졌을때의 위치를 관리하고(control) , 마지막 하나는 현재 M개의 조합에서의 방문 상태(visited)를 관리한다.

 

다음으로 BFS를 통해서 모든 시간을 int 2차원 배열인 map에 기록하고 map의 각 위치를 확인해서 1. visited 배열과 control 배열이 같다면 총 시간과 비교해서 높은것을 고르고, 2. virus 배열을 통해서 원래 바이러스 위치가 아니라면 답과 최솟값 비교를 하지 않는 방식으로 작성하면 된다. 마지막으로 답이 한번도 변경되지 않은 상태 (answer == Integer.MAX_VALUE) 라면 -1을 출력한다.

 

 

Java 풀이

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

class Main {
    static boolean[][] visited;
    static boolean[][] virus;
    static boolean[][] control;
    static int[][] graph;
    static ArrayList<Node> dots = new ArrayList<>();
    static ArrayList<ArrayList<Node>> cur = new ArrayList<>();
    static int answer = Integer.MAX_VALUE;
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

    static class Node {
        int x, y, timeA, timeB, type;

        public Node(int x, int y, int timeA, int timeB, int type) {
            this.x = x;
            this.y = y;
            this.timeA = timeA;
            this.timeB = timeB;
            this.type = type;
        }
    }

    public static void combination(ArrayList<Node> list, int count, int index) {
        if (count == 0) {
            cur.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < dots.size(); i++) {
            list.add(dots.get(i));
            combination(list, count - 1, i + 1);
            list.remove(list.size() - 1);
        }
    }

    private static void bfs(int n, ArrayList<Node> nodes) {
        int[][] map = new int[n][n];
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        LinkedList<Node> q = new LinkedList<>();
        for (int i = 0; i < nodes.size(); i++) {
            Node curNode = nodes.get(i);
            q.add(new Node(curNode.x, curNode.y, curNode.timeA, curNode.timeB, curNode.type));
            visited[curNode.x][curNode.y] = true;
            map[curNode.x][curNode.y] = curNode.timeA;
        }

        while (!q.isEmpty()) {
            Node node = q.removeFirst();
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i], ny = node.y + dy[i];
                if (nx < 0 || nx >= n | ny < 0 || ny >= n) continue;
                if (graph[nx][ny] == 0 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    map[nx][ny] = node.timeA + 1;
                    q.add(new Node(nx, ny, node.timeA + 1, node.timeB + 1, 0));
                }
                if (graph[nx][ny] == 2 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    map[nx][ny] = node.timeB;
                    q.add(new Node(nx, ny, node.timeA + 1, node.timeB, 2));
                }
            }
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == control[i][j]) {
                    count = Math.max(count, map[i][j]);
                } else {
                    if (!virus[i][j]) {
                        return;
                    }
                }
            }
        }

        answer = Math.min(answer, count);
    }

    public static void main(String[] args) {
        FastReader sc = new FastReader();

        int n = sc.nextInt(), m = sc.nextInt();
        graph = new int[n][n];
        control = new boolean[n][n];
        virus = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
                if (graph[i][j] == 2) {
                    dots.add(new Node(i, j, 0, 0, 2));
                    control[i][j] = true;
                    virus[i][j] = true;
                }
                if (graph[i][j] == 0) {
                    control[i][j] = true;
                }
            }
        }

        combination(new ArrayList<>(), m, 0);

        for (int i = 0; i < cur.size(); i++) {
            visited = new boolean[n][n];
            bfs(n, cur.get(i));
        }

        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }
}

위에서는 time을 두개로 나누어 관리했지만 굳이 time을 나누어서 관리하지 않아도 된다.