백준 14502번 : 연구소 자바

 

 

🧫 문제 분석

 

 

✔️ 출처

연구소 골드 4

 

📖 문제

 

완전탐색  + BFS 문제이다. ( + 백트래킹...?)

 

단순하게 0인 곳에서 1을 세우되 3개까지만 세우고 BFS로 탐색해보고 퍼진 바이러스 개수의 최솟값을 구한다. 

1을 세우는 것은 모든 구역에 대해서 진행하면 된다. 

 

1로 된 벽 개수를 세고

바이러스 위치를 list에 담고

안전한 구역을 zeroList에 담는다. 

 

list는 bfs에서 빠르게 사용하기 위함이고,

zeroList는 완전탐색을 빠르게 하기 위함이다.

 

전체 크기 - (벽의 개수 + 새롭게 세운 벽 3개 + 바이러스 개수의 최솟값) 이 안전구역의 최댓값이다.

 

 

---

🔅 문제 풀이

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

public class Main {
    static int[][] graph;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int virusCount = Integer.MAX_VALUE;
    static ArrayList<int[]> list = new ArrayList<>();
    static ArrayList<int[]> zeroList = new ArrayList<>();

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int wallCount = 0;

        graph = new int[n][m];
        
        // 그래프 초기화
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 1) wallCount++;
                else if (graph[i][j] == 2) list.add(new int[]{i, j});
                else zeroList.add(new int[]{i, j});
            }
        }

        dfs(0, 0);

        bw.write( ((n * m) - (wallCount + virusCount + 3)) + "");
        bw.flush();
        bw.close();
    }

    private static void dfs(int start, int depth) {

        if (depth == 3) {
            int newVirus = bfs(copyArray(graph));
            virusCount = Math.min(virusCount, newVirus);
            return;
        }

        for (int i = start; i < zeroList.size(); i++) {
            int[] tmp = zeroList.get(i);
            graph[tmp[0]][tmp[1]] = 1;
            dfs(i + 1, depth + 1);
            graph[tmp[0]][tmp[1]] = 0;
        }
    }

    private static int bfs(int[][] map) {

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

        for (int[] ints : list) {
            q.add(ints);
        }

        while (!q.isEmpty()) {
            int[] loc = q.poll();
            count++;

            for (int i = 0; i < 4; i++) {

                int nextY = loc[0] + dy[i];
                int nextX = loc[1] + dx[i];

                if (nextY < 0 || nextY >= map.length ||
                        nextX < 0 || nextX >= map[0].length ) continue;

                if (map[nextY][nextX] == 0) {
                    map[nextY][nextX] = 2;
                    q.add(new int[] {nextY, nextX});
                }
            }
        }

        return count;
    }

    private static int[][] copyArray(int[][] arr) {
        int[][] tmp = new int[arr.length][arr[0].length];

        for (int i = 0; i < arr.length; i++) {
            tmp[i] = arr[i].clone();
        }
        return tmp;
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  매개변수로 넘어온 수를 반복문 초기 변수로 사용할 때는 항상 어떻게 돌아가는지 생각해야한다.