[백준 14502번] 연구소 :: 늦깎이 IT

[백준 14502번] 연구소

1. 벽을 3개 세우기 위해 DFS 완전탐색을 시작한다.

2. 중복을 피하기 위해, 현재 시작점으로부터 오른쪽, 아래쪽 방향으로만 탐색을 진행한다.

3. 벽을 3개 세웠으면, 그 상태에서 BFS 탐색으로 바이러스를 퍼뜨린다.

4. 바이러스를 모두 퍼뜨렸으면, 안전지대를 세서 출력한다.

[중복이 발생하는 코드]

public static void dfs(int numOfWall, int[][] prev) {
 
        int[][] temp = new int[N][M];
        for (int i = 0; i < N; i++)
            temp[i] = Arrays.copyOf(prev[i], prev[i].length);
 
        if (numOfWall == 3) {
            bfs(temp);
            ans = Math.max(ans, countSafety(temp));
            return;
        }
        
        for (int i = 0; i < N; i++) {
 
            for (int j = 0; j < M; j++) {
 
                if (temp[i][j] == 0) {
 
                    temp[i][j] = 1;
                    dfs(numOfWall + 1, temp);
                    temp[i][j] = 0;
                }
            }
        }
    }

[중복이 발생하지 않는 코드]

public static void dfs(int start, int numOfWall, int[][] prev) {
 
        int[][] temp = new int[N][M];
        for (int i = 0; i < N; i++)
            temp[i] = Arrays.copyOf(prev[i], prev[i].length);
 
        if (numOfWall == 3) {
            bfs(temp);
            ans = Math.max(ans, countSafety(temp));
            return;
        }
 
        for (int i = start; i < N * M; i++) {
 
            int row = i / M;
            int col = i % M;
 
            if (temp[row][col] == 0) {
                temp[row][col] = 1;
                dfs(i + 1, numOfWall + 1, temp);
                temp[row][col] = 0;
            }
        }
    }

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int N, M, ans = 0;
    public static int[][] map;
    public static int[] dirX = new int[] { 0, 0, 1, -1 }; // 동 서 남 북
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        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, 0, map);
        System.out.println(ans);
 
    }
 
    public static void bfs(int[][] prev) {
 
        Queue<Node> q = new LinkedList<>();
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (prev[i][j] == 2) {
                    q.offer(new Node(i, j));
                }
            }
        }
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
 
            for (int i = 0; i < 4; i++) {
 
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && prev[nr][nc] == 0) {
                    prev[nr][nc] = 2;
                    q.offer(new Node(nr, nc));
                }
            }
        }
 
    }
 
    public static void dfs(int start, int numOfWall, int[][] prev) {
 
        int[][] temp = new int[N][M];
        for (int i = 0; i < N; i++)
            temp[i] = Arrays.copyOf(prev[i], prev[i].length);
 
        if (numOfWall == 3) {
            bfs(temp);
            ans = Math.max(ans, countSafety(temp));
            return;
        }
 
        for (int i = start; i < N * M; i++) {
 
            int row = i / M;
            int col = i % M;
 
            if (temp[row][col] == 0) {
                temp[row][col] = 1;
                dfs(i + 1, numOfWall + 1, temp);
                temp[row][col] = 0;
            }
        }
    }
 
    public static int countSafety(int[][] map) {
 
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0)
                    count += 1;
            }
        }
        return count;
    }
 
    public static void showMap(int[][] prev) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(prev[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < M);
    }
 
}
 
class Node {
 
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}