Q. 14502 연구소

Q. 14502 연구소

 

문제 : boj.kr/14502

골드 4 난이도의 문제이다.

 

바이러스(2) 벽(1) 빈 공간(0)을 의미하는 격자형 그래프가 주어지고,

바이러스는 빈 공간이 있으면 확산된다는 조건이 있다.

이 때 벽을 세 개 세워서 바이러스의 확산을 최대한 막는 방법을 물어보는 문제이다.

 

처음 문제를 봤을 때 든 생각은 벽을 세울 수 있는 모든 경우의 수를 dfs로 구현한 뒤

벽을 3개 만들었을 경우, 바이러스를 확산시켜 빈 공간의 수를 계산하는 방식을 떠올렸다.

근데 막상 구현을 하다 보니 너무 복잡해지는 것 같아 생각을 바꿨다.

 

아래와 같은 방식으로 구현을 했다.

1. 빈 공간(0)을 리스트에 모두 저장한다.

2. 벽을 최대 3개 세울 수 있으므로 3중for문을 이용해 벽을 세울 수 있는 모든 경우의 수를 구한다.

3. 벽을 3개 세웠을 때마다 바이러스가 확산됬을 때의 빈 공간의 수를 구한다.

사실 N, M의 최대값이 8이라 가능한 풀이 방식이고,

이 문제의 분류 중 브루트포스 알고리즘이 있어서 떠올린 방식이다.

 

세로, 가로가 N, M으로 주어지므로 시간복잡도는 아래와 같다.

1. 그래프중 0인 리스트를 저장 - O(N * M)

2. 3중 for문을 통해 가능한 벽의 위치를 저장 - 최악의 경우O(N^3 * M^3) 

3. 만약 벽을 3개 세운 경우 BFS를 이용해 바이러스 확산 시 남은 빈 공간의 수 계산

이 경우 위의 시간복잡도에 곱해줘야 함 - O(N * M)

따라서 약 O(N^4 * M^4)으로 최악의 경우 약 8^8 = 16777216번 계산을 하면 답을 구할 수 있고,

시간초과는 걱정하지 않아도 된다

 

이 문제는 강의를 듣기 전에 나만의 방식으로 풀어본 것 이고,

내가 생각해도 3중 for문은 비효율적이라고 생각해서(약 O(N^8)의 풀이) 강의를 들어보고

좀 더 개선할 방향이 있는지 생각해봐야겠다,

 

풀고난 뒤 for문에 M, N값을 잘못 넣어서 런타임 에러가 나서 삽질을 해서 좀 더 슬픈 문제였다..

---

내 풀이는 아래와 같다

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


public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static int cnt = 0;
    static int[][] graph;

    static int[] dy = new int[] {0, 1, 0, -1};
    static int[] dx = new int[] {1, 0, -1, 0};

    static List<int[]> zeroList;

    static void input() {

        N = scan.nextInt();
        M = scan.nextInt();
        graph = new int[N][M];
        zeroList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                graph[i][j] = scan.nextInt();
                if (graph[i][j] == 0) zeroList.add(new int[] {i, j});
            }
        }
    }

    static void bfs() {

        boolean[][] visit = new boolean[N][M];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (graph[i][j] != 0){
                    visit[i][j] = true;
                    if (graph[i][j] == 2) queue.add(new int[] {i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                if (ny < 0 || nx < 0 || ny == N || nx == M) continue;
                if (visit[ny][nx]) continue;
                visit[ny][nx] = true;
                queue.add(new int[]{ny, nx});
            }
        }

        int blankCnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) if (graph[i][j] == 0 && !visit[i][j]) blankCnt++;
        }

        cnt = Math.max(blankCnt, cnt);
    }

    static void pro() {
        for (int i = 0; i < zeroList.size() - 2; i++) {
            int[] a = zeroList.get(i);
            graph[a[0]][a[1]] = 1;
            for (int j = i + 1; j < zeroList.size() - 1; j++) {
                int[] b = zeroList.get(j);
                graph[b[0]][b[1]] = 1;
                for (int k = j + 1; k < zeroList.size(); k++) {
                    int[] c = zeroList.get(k);
                    graph[c[0]][c[1]] = 1;
                    bfs();
                    graph[c[0]][c[1]] = 0;
                }
                graph[b[0]][b[1]] = 0;
            }
            graph[a[0]][a[1]] = 0;
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        // BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

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

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        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());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}