[JAVA] 백준 연구소 DFS+BFS

DFS + BFS를 이용한 문제의 대표유형이다.

 

DFS는 depth를 인수로 재귀를 돌고,

BFS는 Queue를 이용하여 queue.isEmpty()를 이용하여 재귀를 돌린다.

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

각각의 주석을 통해 dfs와 bfs의 대표적인 풀이법을 살펴보면 도움이 될 듯하다.

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

class Main {
    static int[][] grid;
    static int N, M;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        grid = new int[N + 1][M + 1];
        for (int i = 1; i < N + 1; i++) {
            s = br.readLine();
            String[] split = s.split(" ");
            for (int j = 1; j < M + 1; j++) {
                grid[i][j] = Integer.parseInt(split[j - 1]);
            }
        }
        dfs(0);
        System.out.println(max);
    }

    //1. dfs로 벽세우기
    static void dfs(int depth) {
        if (depth == 3) {
            bfs();
            return;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (grid[i][j] == 0) {
                    grid[i][j] = 1;
                    dfs(depth + 1);
                    grid[i][j] = 0;
                }
            }
        }
    }

    //bfs 준비물
    static int[] dr = {-1, 1, 0, 0};//상하좌우
    static int[] dc = {0, 0, -1, 1};//상하좌우
    static class virus {
        int r,c;
        virus(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    //2. bfs로 바이러스 퍼트리기
    static void bfs() {
        int[][] map = new int[N + 1][M + 1];
        //배열복사
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                map[i][j] = grid[i][j];
            }
        }

        //먼저 큐에 바이러스 근원지들을 넣어놓고 각각에 대하여 bfs
        Queue<virus> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if(map[i][j] == 2) q.offer(new virus(i,j));
            }
        }

        //bfs시작
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                while (!q.isEmpty()) {
                    virus v = q.poll();
                    for(int d=0; d<4; d++) {
                        int r = v.r+dr[d];
                        int c = v.c+dc[d];
                        if(r>0&&r<=N&&c>0&&c<=M){
                            if(map[r][c] == 0) {
                                map[r][c] = 2;
                                q.offer(new virus(r, c));
                            }
                        }
                    }
                }
            }
        }
        //bfs끝나면 안전지역찾기
        safeZone(map);
    }

    //3. safe존 확인
    static void safeZone(int[][] map){
        int count=0;
        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                if(map[i][j] == 0) count++;
            }
        }

        max = Math.max(max,count);
    }
}