백준 14502 연구소 JAVA

 

DFS와 BFS를 동시에 활용해야 하는 문제인 백준 14502-연구소 문제를 풀어보자.

(solved.ac 티어 = 골드 5)

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

 

1. 접근

그래프의 크기는 N * M이며 

N과 M의 최댓값은 8이다.

 

문제에서 확인할 수 있듯 그래프의 크기는 8 * 8 = 64가지이며

 

 

바이러스의 확산을 막는 벽을 반드시 3개를 설치해야 한다.

 

즉 우리가 해야 할 일은

벽을 3개 세워본다 -> 바이러스를 퍼트린다(0인 곳)  -> 남아있는 안전지역을 확인한다 -> 최 갯값을 갱신한다.

 

이렇게 네 가지로 정리할 수 있으며

최댓값인 64개의 공간에 중복되지 않게 벽을 3개 세워본다 = n! / ((n - m)! * m!) = 41664

벽을 세운 후 하나하나 탐색하며 안전지대인지 확인한다 = N² = 64

 

시간 복잡도 = 41664 * 64 = 약 266만으로 시간제 한인 2초 안에 문제를 풀 수 있다.

 

2. 풀이

 

input 및 전역 변수 세팅

 

벽을 세울 수 있는 위치 저장

 

벽을 세울 수 있는 조합 확인

 

바이러스 확산 및 안전지대 카운트

3. 전체 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static class Virus {
        int x, y;

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

    static int N, M, B, answer;
    static int[][] A, blank;
    static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 바이러스가 퍼질 수 있는 범위
    static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 가로 크기
        M = Integer.parseInt(st.nextToken()); // 세로 크기
        A = new int[N + 1][M + 1]; // 해당 좌표의 상태값
        blank = new int[N * M + 1][2]; // 벽을 세울 수 있는 위치
        visit = new boolean[N + 1][M + 1]; // 방문 여부
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        solution();
    }

    static void solution() {
        // 2중 for문을 통해 벽을 세울 수 있는 좌표를 담아두자!
        // B == 벽을 세울 수 있는 위치의 갯수
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (A[i][j] == 0) {
                    B++;
                    blank[B][0] = i;
                    blank[B][1] = j;
                }
            }
        }
        // 벽을 세워보자!
        DFS(1, 0);
        System.out.println(answer);
    }

    // 벽을 세울 수 있는 경우의 수에 다 세워보자
    static void DFS(int idx, int selectCnt) {
        if (selectCnt == 3) { // 3개의 벽을 모두 세웠다!!
            BFS(); // 바이러스를 퍼뜨려 보자!
            return;
        }
        if (idx > B) return; // 더 이상 벽을 세울 수 없다!!

        // 벽을 세웠을 경우
        A[blank[idx][0]][blank[idx][1]]= 1;
        DFS(idx + 1, selectCnt + 1);
        A[blank[idx][0]][blank[idx][1]]= 0;
        // 세우지 않았을 경우
        DFS(idx + 1, selectCnt);
    }

    // 벽을 모두 세웠다면 바이러스를 퍼뜨려보자!
    static void BFS() {
        Queue<Virus> Q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                // 다른 경우의 수에 의해 BFS 들어왔을때를 위해 false로 초기화
                Virus virus = new Virus(i, j);
                visit[i][j] = false;
                if (A[i][j] == 2) {
                    Q.add(virus); // 바이러스 좌표
                    visit[i][j] = true;
                }
            }
        }

        while(!Q.isEmpty()) {
            Virus virus = Q.poll();
            for (int k = 0; k < 4; k++) {
                int nx = virus.x + dir[k][0];
                int ny = virus.y + dir[k][1];
                if (nx < 0 || ny < 0 || nx > N || ny > M) continue; // 배열범위 초과
                if (A[nx][ny] != 0) continue; // 빈 공간이 아니면 확산하지 못한다.
                if (visit[nx][ny]) continue; // 이미 방문하였다.
                visit[nx][ny] = true;
                Q.add(new Virus(nx, 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++;
                }
            }
        }
        // 최댓값 갱신
        answer = Math.max(answer, cnt);
    }
}

 

코드나 풀이 방식에 대한 지적은 환영합니다!