[알고리즘] 백준 14502번 연구소 :: 우유

코드 설명

문제 포인트는
1. 3개의 벽을 세울 수 있는 모든 경우의 수를 구해서 새롭게 복사한 COPY_MAP을 각각 만드는 것
여기서 세울 수 있는 경우의 수가 엄청 많은데 이를 하나하나 다 BFS를 돌려봐야 한다.
2. 1번에서 새운 MAP 에서 BFS 돌려서 안전거리의 영역을 카운트해서 그 안전거리의 최대값을 출력

DFS와 BFS 를 동시에 연습할수 있는 아주 좋은 문제였다.
 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int[][] map;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int ans = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        DFS(0);

        System.out.println(ans);
    }

    public static void DFS(int cnt) {
        if (cnt == 3) {
            BFS();
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    DFS(cnt + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

    public static void BFS() {
        // 벽을 새로 새울떄마다 배열 초기화
        int[][] copy_map = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copy_map[i][j] = map[i][j];
            }
        }
        Queue<Node> qu = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copy_map[i][j] == 2) {
                    qu.add(new Node(i, j));
                }
            }
        }

        while (!qu.isEmpty()) {
            Node curNode = qu.poll();

            for (int i = 0; i < 4; i++) {
                int ny = curNode.y + dy[i];
                int nx = curNode.x + dx[i];

                if (ny < 0 || nx < 0 || N <= ny || M <= nx) continue;

                if (copy_map[ny][nx] == 0) {
                    copy_map[ny][nx] = 2;
                    qu.add(new Node(ny, nx));
                }


            }

        }
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copy_map[i][j] == 0) {
                    cnt++;
                }
            }
        }
        ans = Math.max(cnt, ans);
    }


    public static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

}