[백준] 14502번 연구소 java[브루트포스, 탐색][엄탱]

문제 링크

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

14502번: 연구소

문제 풀이

백준 14502번 연구소 문제는 두 가지만 어떤 방식으로 풀지 알면 그 뒤로는 금방 풀 수 있다.

3개의 벽을 어떻게 설치할지, 바이러스 퍼지는 영역을 어떻게 찾을지만 생각해보고 코드를 보면 이해하기 쉽다.

• 브루트포스 알고리즘(직접구현 또는 DFS): 3개의 벽을 설치할 때 사용
• 너비 우선 탐색(BFS): 바이러스가 퍼지는 영역을 찾는 데 사용

시간복잡도를 생각해보자

지도의 최대 크기 = 8 * 8 = 64
바이러스 퍼지는 최대 영역 = 지도 최대 크기
벽 1개를 설치하는 경우의 수 = 64
벽 2개를 설치하는 경우의 수 = 64 * 64 = 4,096
벽 3개를 설치하는 경우의 수 = 64 * 64 * 64 = 262,144
벽 3개를 설치하고 바이러스 퍼지는 영역을 검사하는 최대 경우의 수 = 262,144 * 64 = 16,777,216

시간제한은 2초이고 경우의 수가 최대 1억을 넘지 않으니 가능한 것으로 보인다.

코드(DFS)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N; // 행의 개수 (세로 길이)
    static int M; // 열의 개수 (가로 길이)
    static int[][] board; // 연구소 지도
    static int zeroCount = 0; // 처음 연구소에서 0개의 개수
    static int max = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());

                if (board[i][j] == 0) {
                    zeroCount++;
                }
            }
        }
        
        wallDFS(0, 0);
        
        System.out.println(max);
        br.close();
    }
    public static void wallDFS(int count, int index) {
        if (count == 3) {
            max = Math.max(max, zeroCount - birusCountBFS() - 3);
            return;
        }
        
        for (int i = index; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0) {
                    board[i][j] = 1;
                    wallDFS(count + 1, i);
                    board[i][j] = 0;
                }
            }
        }
    }

    public static int birusCountBFS() {
        int count = 0;

        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 2) {
                    q.offer(new int[]{i, j});
                }
            }
        }

        boolean[][] visited = new boolean[N][M];

        while(!q.isEmpty()) {
            int[] cur = q.poll();

            int x = cur[0];
            int y = cur[1];

            if (visited[x][y]) {
                continue;
            }

            if (board[x][y] == 0) {
                count++;
            }

            visited[x][y] = true;

            if (x - 1 >= 0 && !visited[x - 1][y] && board[x - 1][y] == 0) {
                q.offer(new int[]{x - 1, y});
            }

            if (x + 1 < N && !visited[x + 1][y] && board[x + 1][y] == 0) {
                q.offer(new int[]{x + 1, y});
            }

            if (y - 1 >= 0 && !visited[x][y - 1] && board[x][y - 1] == 0) {
                q.offer(new int[]{x, y - 1});
            }

            if (y + 1 < M && !visited[x][y + 1] && board[x][y + 1] == 0) {
                q.offer(new int[]{x, y + 1});
            }
        }

        return count;
    }
}

코드(DFS를 사용하지 않고 구현)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N; // 행의 개수 (세로 길이)
    static int M; // 열의 개수 (가로 길이)
    static int[][] board; // 연구소 지도
    static int zeroCount = 0; // 처음 연구소에서 0개의 개수
    static int max = 0;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());

                if (board[i][j] == 0) {
                    zeroCount++;
                }
            }
        }
        
        for (int i = 0; i < N; i++) {
            for (int _i = 0; _i < M; _i++) {
                if (board[i][_i] == 0) {
                    board[i][_i] = 1;

                    for (int j = i; j < N; j++) {
                        for (int _j = 0; _j < M; _j++) {
                            if (board[j][_j] == 0) {
                                board[j][_j] = 1;

                                for (int k = j; k < N; k++) {
                                    for (int _k = 0; _k < M; _k++) {
                                        if (board[k][_k] == 0) {
                                            board[k][_k] = 1;
                                            int count = birusCountBfs();
                                            max = Math.max(max, zeroCount - count - 3);
                                            board[k][_k] = 0;
                                        }
                                    }
                                }

                                board[j][_j] = 0;
                            }
                        }
                    }

                    board[i][_i] = 0;
                }
            }
        }
        
        System.out.println(max);
        br.close();
    }

    public static int birusCountBfs() {
        int count = 0;

        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 2) {
                    q.offer(new int[]{i, j});
                }
            }
        }

        boolean[][] visited = new boolean[N][M];

        while(!q.isEmpty()) {
            int[] cur = q.poll();

            int x = cur[0];
            int y = cur[1];

            if (visited[x][y]) {
                continue;
            }

            if (board[x][y] == 0) {
                count++;
            }

            visited[x][y] = true;

            if (x - 1 >= 0 && !visited[x - 1][y] && board[x - 1][y] == 0) {
                q.offer(new int[]{x - 1, y});
            }

            if (x + 1 < N && !visited[x + 1][y] && board[x + 1][y] == 0) {
                q.offer(new int[]{x + 1, y});
            }

            if (y - 1 >= 0 && !visited[x][y - 1] && board[x][y - 1] == 0) {
                q.offer(new int[]{x, y - 1});
            }

            if (y + 1 < M && !visited[x][y + 1] && board[x][y + 1] == 0) {
                q.offer(new int[]{x, y + 1});
            }
        }

        return count;
    }
}

기타

근데 항상 브루트포스 알고리즘으로 생각하는 게 더 어렵다.

'이렇게 하나하나 해도 될까? 아니야 안될 것 같아' 라는 생각 때문에 분명 시간초과가 날 것 같고 안될것 같다.

그래서 항상 브루트포스 문제로 접근해서 습관을 만들고 그다음 시간초과가 나면 어떻게 하면 효율적으로 풀 수 있을지 생각해보는 게 좋은 것 같다. 

물론, 시간복잡도를 계산하고 브루트포스 문제를 푸는 게 좋은 것 같다.