백준 14502 연구소 - JAVA

14502 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

<BFS>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int[][] arr;
    static List<int[]> zero = new ArrayList<>();
    static List<int[]> virus = new ArrayList<>();
    static int MaxArea = 0;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    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());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N+1][M+1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 0) {
                    zero.add(new int[] {i, j});
                } else if (arr[i][j] == 2) {
                    virus.add(new int[] {i, j});
                }
            } 
        } 
        combination(0, 0);
        bw.write(String.valueOf(MaxArea));
        bw.flush();
    }
    private static void bfs() {
        int[][] tempMap = new int[N+1][M+1];
        for (int i = 0; i <= N; i++) {
            tempMap[i] = arr[i].clone();
        } 
        Queue<int[]> queue = new LinkedList<>(virus);
        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                if (nx > 0 && ny > 0 && nx <= N && ny <= M && tempMap[nx][ny] == 0) {
                    tempMap[nx][ny] = 2;
                    queue.offer(new int[] {nx, ny});
                } 
            } 
        }
        int safeArea = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (tempMap[i][j] == 0) {
                    safeArea++;
                } 
            } 
        } 
        MaxArea = Math.max(MaxArea, safeArea);
    }
    private static void combination(int start, int count) {
        if (count == 3) {
            bfs();
            return;
        } 
        for (int i = start; i < zero.size(); i++) {
            int[] temp = zero.get(i);
            arr[temp[0]][temp[1]] = 1;
            combination(i+1, count+1);
            arr[temp[0]][temp[1]] = 0;
        } 
    }
}

 

<DFS>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int[][] arr;
    static List<int[]> zero = new ArrayList<>();
    static List<int[]> virus = new ArrayList<>();
    static int MaxArea = 0;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    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());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N+1][M+1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 0) {
                    zero.add(new int[] {i, j});
                } else if (arr[i][j] == 2) {
                    virus.add(new int[] {i, j});
                }
            } 
        } 
        combination(0, 0);
        bw.write(String.valueOf(MaxArea));
        bw.flush();
    }
    private static void dfs(int x, int y, int[][] tempMap) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx > 0 && ny > 0 && nx <= N && ny <= M) {
                if (tempMap[nx][ny] == 0) {
                    tempMap[nx][ny] = 2;
                    dfs(nx, ny, tempMap);
                }
            } 
        } 
    }
    private static void combination(int start, int count) {
        if (count == 3) {
            int[][] tempMap = new int[N+1][M+1];
            for (int i = 0; i <= N; i++) {
                tempMap[i] = arr[i].clone();
            } 
            for (int[] i : virus) {
                dfs(i[0], i[1], tempMap);
            } 
            int safeArea = 0;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (tempMap[i][j] == 0) {
                        safeArea++;
                    } 
                } 
            } 
            MaxArea = Math.max(safeArea, MaxArea);
            return;
        } 
        for (int i = start; i < zero.size(); i++) {
            int[] temp = zero.get(i);
            arr[temp[0]][temp[1]] = 1;
            combination(i+1, count+1);
            arr[temp[0]][temp[1]] = 0;
        } 
    }
}

 

알고리즘 설명

---

좌표에서 벽을 3개 세워야 하는 방식은 기존의 세워져 있는 벽에 따라서 결과값이 언제든지 바뀔 수 있기때문에, 좌표 내에 세울 수 있는 벽 3개의 모든 경우의 수를 계산해야합니다. 흔히 말해 브루트 방식과 경로탐색 알고리즘을 조합해야 하는 문제입니다. 해당 문제에서 벽을 세울 경우의 수를 모두 계산했다면, 기본적으로 BFS와 DFS둘 중 한가지의 탐색 방식을 선정하여 길찾기를 할 수 있는데, 해당 문제에서는 바이러스의 개수가 정해져있지 않기때문에, 바이러스의  개수가 몇 개이던 최대 깊이를 유지하는 DFS와 다르게 BFS는 그래프내에 배치된 바이러스의 개수가 많다면 큐에 들어가는 개수자체가 많아져 큐의 크기자체가 커지므로, 상대적으로 DFS에 비해 많은 메모리를 차지할 수 있습니다. 위의 두 가지 방식에 대한 메모리 사용량의 차이를 보여드리겠습니다.

아래에서부터 BFS, DFS

이후, 벽 3개를 배치한 경우의 수에 따라 DFS/BFS로 0의 개수를 구했다면, 가장 0의 개수가 많은 그래프가 안전영역의 크기가 가장 큰 것이기 때문에, 각 경우별로 최대값을 계산하여 최종적으로 가장 큰 값을 출력합니다.

 

코드 해석

---

N, M과 arr 2차원 배열을 생성해 그래프를 입력하고 combination 메서드를 생성하여 가능한 모든 벽 배치의 경우의 수를 생성합니다. 생성된 경우의 수를 각각의 tempMap이라는 그래프로 복사하고 DFS/BFS 함수에 그래프를 집어넣어 0의 개수를 출력합니다. 함수가 종료된 후, 존재하는 0의 개수를 MaxArea로 갱신하여 출력합니다.