(Java) 백준 14502 - 연구소

골드 4 문제인데 정답률이 높아서 도전한 문제이다.

DFS와 BFS 문제 심화 버전? 같은 느낌이었고 2시간 정도 걸렸다.

처음에는 벽을 세우는 로직에 대해서 고민을 했었다.

2를 기준으로 세우는 알고리즘과 1을 기준으로 세우는 알고리즘을 한참을 생각해봤지만

떠오르지 않았다.

 

시간제한이 2초이고 M이 8이하로 입력되니 그냥 모든 벽을 세우는 완전 탐색으로 진행했다.

1. 완전 탐색으로 모든 벽을 세워본다.

2. BFS로 바이러스를 퍼트린다.

3. 남아있는 0을 센다.

 

이렇게 로직을 작성했고 코드로 구현하는데 한시간정도 걸렸던 것 같다.

나머지 한시간은 연속적으로 메서드를 호출하는 과정에서 배열의 값이 꼬이는 걸 해결하는데 썼다.

3개의 메서드가 연속적으로 호출되는데 이렇게 구현한적은 처음이라서 시간이 오래 걸렸던 것 같다.

다른 분들보다 시간이 좀 더 걸렸지만 결국 성공했다.

처음으로 검색없이 골드 4 문제를 해결해서 기분이 좋았지만

실제 코테였다면 한 문제 풀고 끝났을 것이기 때문에

풀이 시간을 줄이는게 관건일 것 같다.

---

최종 코드 

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

// 벽을 세우는 알고리즘 -> 모르겠는데 재귀로 완탐하자
// 바이러스를 퍼트리는 알고리즘 (BFS)
// 0을 세는 알고리즘 (탐색)

public class Main {
    static int n, m;
    static int[][] arr;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] virusVisited;
    static List<int[]> list;
    static List<Integer> cntList;

    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());
        arr = new int[n][m];
        boolean[][] visited = new boolean[n][m];
        virusVisited = new boolean[n][m];
        list = new ArrayList<>();
        cntList = new ArrayList<>();

        // 입력값 배열 삽입
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 2) {
                    list.add(new int[]{i, j});
                }
            }
        }

        // 첫 메서드 호출
        wall(arr, visited, 0);

        // 리스트에서 가장 큰 수 뽑기
        int max = Collections.max(cntList);
        System.out.println(max);

    }

    // 완전탐색으로 벽 쌓는 메서드
    static void wall(int[][] array, boolean[][] visit, int depth) {
        // 벽 3개를 세웠다면
        if (depth == 3) {
            // array를 복사해서 다음 메서드로 넘겨줌 (clone으로는 깊은 복사 안됨)
            int[][] arrayTemp = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arrayTemp[i][j] = array[i][j];
                }
            }

            // 바이러스 메서드 호출
            virus(arrayTemp);
            return;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (array[i][j] == 0 && !visit[i][j]) {
                    visit[i][j] = true;
                    array[i][j] = 1;
                    wall(array, visit, depth + 1);
                    array[i][j] = 0;
                    visit[i][j] = false;
                }
            }
        }
    }

    // BFS를 통해 바이러스 퍼트리는 메서드
    static void virus(int[][] array) {
        // 바이러스가 포함된 좌표 불러오기
        for (int[] temp : list) {
            // BFS
            Queue<int[]> queue = new LinkedList();
            queue.add(temp);

            while (!queue.isEmpty()) {
                int[] qTemp = queue.poll();
                virusVisited[temp[0]][temp[1]] = true;
                for (int i = 0; i < 4; i++) {
                    int nx = qTemp[0] + dx[i];
                    int ny = qTemp[1] + dy[i];

                    if(nx < 0 || ny < 0 || nx >= n || ny >= m) {
                        continue;
                    }

                    if(array[nx][ny] == 0 && !virusVisited[nx][ny]) {
                        virusVisited[nx][ny] = true;
                        array[nx][ny] = 2;
                        queue.add(new int[] {nx, ny});
                    }
                }
            }
        }
        // cal 메서드 호출
        cal(array);
        // 사용한 배열 초기화
        virusVisited = new boolean[n][m];
    }

    // 남아있는 0이 몇개인지 세는 메서드
    static void cal(int[][] array) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(array[i][j] == 0) {
                    cnt++;
                }
            }
        }
        // list에 저장
        cntList.add(cnt);
    }
}