(JAVA) [BOJ]백준 14502번, 연구소

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

14502번: 연구소

 

14502, 연구소

📌 난이도 : Gold 4

📌 알고리즘 : BFS & DFS

 

이번 문제는 Multi-Source BFS 문제이다. 벽 3개를 두어서 안전 공간을 최대한 확보하는 것이 중요하다. 그렇기에 빈 공간에 차례로 벽 3개를 두는 경우를 탐색하며 BFS 로 안전 공간을 구하는 로직을 구현하겠다.

🧩 프로세스

📚 초기화 및 선언

: 빈 공간을 확인할 int[] blank 를 선언해준다. 이는 전체 넓이이기 때문에 N*M+1로 공간을 잡아준다.

static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();

static int N, M, B, ans;
static boolean[][] visit;
static int[][] A, blank;
static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

static void input() {
    N = scan.nextInt();
    M = scan.nextInt();
    A = new int[N + 1][M + 1];
    // 빈칸 (벽을 놓을 수 있는 공간), 벽의 개수이기 때문에 전체 넓이 (+1)
    blank = new int[N * M + 1][2]; 
    visit = new boolean[N + 1][M + 1];
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            A[i][j] = scan.nextInt();
            // 빈공간
            if (A[i][j] == 0) {
                B++;
                blank[B][0] = i;
                blank[B][1] = j;
            }
        }
    }
}

 

📚 DFS & BFS

: DFS 를 통해 벽을 3개 세우는 모든 방법을 확인할 것이다.

idx 번째 빈 칸에 벽을 세울 지 말 지 결정하고 selected_cnt 를 통해 3개의 벽을 세웠는 지 확인한다.

벽을 세운 경우와 벽을 세우지 않은 경우, 즉 2가지 경우를 재귀를 통해서 빈 공간의 개수인 B 개만큼 반복해서 모든 경우를 탐색한다.

 

BFS 를 통해서는 바이러스를 퍼트린다. 여기서 Multi-Source BFS 를 사용할 것이다.

모든 바이러스가 시작점으로 가능하기 때문에 전부 큐에 넣어준다. 그리고 기존과 같은 BFS 의 방법을 사용하면 된다.

 

모든 탐색을 마친 후, 해당 구간이 0 이고 방문하지 못한 구역을 체크하면 된다. 

static void pro() {
    dfs(1, 0);
    System.out.println(ans);
}

static void dfs(int idx, int selected_cnt) {
    // 3 개의 벽을 모두 세운 상태
    if (selected_cnt == 3) {
        bfs();
        return;
    }

    // 더 이상 세울 수 있는 벽이 없는 상태
    if (idx > B) return;

    // 벽을 세운 경우의 재귀호출, A = 1
    A[blank[idx][0]][blank[idx][1]] = 1;
    dfs(idx + 1, selected_cnt + 1);

    // 벽을 세우지 않은 경우의 재귀호출, A = 0
    A[blank[idx][0]][blank[idx][1]] = 0;
    dfs(idx + 1, selected_cnt);
}

 static void bfs() {
    Queue<Integer> Q = new LinkedList<>();

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            visit[i][j] = false;
            if (A[i][j] == 2) {
                Q.add(i);
                Q.add(j);
                visit[i][j] = true;
            }
        }
    }

    // BFS 과정
    while (!Q.isEmpty()) {
        int x = Q.poll(), y = Q.poll();
        for (int k = 0; k < 4; k++) {
            int nx = x + dir[k][0], ny = y + dir[k][1];
            if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
            if (A[nx][ny] != 0) continue;
            if (visit[nx][ny]) continue;
            visit[nx][ny] = true;
            Q.add(nx);
            Q.add(ny);
        }
    }

    // 탐색이 종료된 시점이니, 안전 영역의 넓이를 계산하고, 정답을 갱신한다.
    int cnt = 0;

    // 빈칸이고 방문하지 못한 구역을 체크
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            if(A[i][j] == 0 && !visit[i][j]) cnt++;
        }
    }

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

 

✅ 전체 코드

: Multi-Source BFS 는 코딩테스트에 자주 보이는 것 같으니 풀이법을 잘 숙지하면 좋을 것 같다 : )

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

/*
 * 0 => 빈칸
 * 1 => 벽
 * 2 => 바이러스
 */

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

    static int N, M, B, ans;
    static boolean[][] visit;
    static int[][] A, blank;
    static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        A = new int[N + 1][M + 1];
	    // 빈칸 (벽을 놓을 수 있는 공간), 벽의 개수이기 때문에 전체 넓이 (+1)
        blank = new int[N * M + 1][2]; 
        visit = new boolean[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                A[i][j] = scan.nextInt();
                // 빈공간
                if (A[i][j] == 0) {
                    B++;
                    blank[B][0] = i;
                    blank[B][1] = j;
                }
            }
        }
    }

	static void pro() {  
        // 벽을 3개 세우는 모든 방법을 확인해보자!
        dfs(1, 0);
        System.out.println(ans);
	}

    // idx 번째 빈 칸에 벽을 세울 지 말 지 결정해야 하고,
    // 이 전까지 selected_cnt 개의 벽을 세웠다.
    static void dfs(int idx, int selected_cnt) {
        // 3 개의 벽을 모두 세운 상태
        if (selected_cnt == 3) {
            bfs();
            return;
        }

        // 더 이상 세울 수 있는 벽이 없는 상태
        if (idx > B) return;

        // 벽을 세운 경우의 재귀호출, A = 1
        A[blank[idx][0]][blank[idx][1]] = 1;
        dfs(idx + 1, selected_cnt + 1);

        // 벽을 세우지 않은 경우의 재귀호출, A = 0
        A[blank[idx][0]][blank[idx][1]] = 0;
        dfs(idx + 1, selected_cnt);
    }

     // 바이러스 퍼뜨리기!!
     static void bfs() {
        Queue<Integer> Q = new LinkedList<>();

        // 모든 바이러스가 시작점으로 가능하니까, 전부 큐에 넣어준다.
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                visit[i][j] = false;
                if (A[i][j] == 2) {
                    Q.add(i);
                    Q.add(j);
                    visit[i][j] = true;
                }
            }
        }

        // BFS 과정
        while (!Q.isEmpty()) {
            int x = Q.poll(), y = Q.poll();
            for (int k = 0; k < 4; k++) {
                int nx = x + dir[k][0], ny = y + dir[k][1];
                if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
                if (A[nx][ny] != 0) continue;
                if (visit[nx][ny]) continue;
                visit[nx][ny] = true;
                Q.add(nx);
                Q.add(ny);
            }
        }

        // 탐색이 종료된 시점이니, 안전 영역의 넓이를 계산하고, 정답을 갱신한다.
        int cnt = 0;

        // 빈칸이고 방문하지 못한 구역을 체크
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                if(A[i][j] == 0 && !visit[i][j]) cnt++;
            }
        }
        
        ans = Math.max(ans, cnt);
    }

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


    static class FastReader {
        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;
        }
    }
}