[BOJ/Java] 14502. 연구소

[BOJ/Java] 14502. 연구소

14502번: 연구소

---

문제 해석

연구소의 지도가 주어지며, 연구소는 빈 칸, 벽, 바이러스로 구성되어 있다. 벽을 세 개 더 설치하여 바이러스의 확산을 최소화하고, 이때 안전 영역(바이러스가 퍼지지 않은 빈 칸)의 최대 크기를 구하는 것이 문제의 목표이다. 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져 나간다.

풀이 과정

• io 메소드에서 입력을 받아 연구소의 초기 상태를 구성한다. 바이러스 위치는 리스트에 저장한다.
• sol 메소드에서는 벽을 세울 수 있는 모든 조합을 시도하며, 각 조합에 대한 결과를 계산한다.
• bfs 메소드를 통해 바이러스가 퍼지는 상황을 시뮬레이션하고, countSafe 메소드로 안전 영역의 크기를 계산한다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No14502;

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

public class Main {
    private int[][] graph; // 연구소의 지도
    private List<Point> virusList; // 바이러스의 위치 리스트
    private int ans = Integer.MIN_VALUE; // 계산된 최대 안전 영역의 크기
    private static final int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 네 방향에 대한 벡터
    boolean[][] visited; // 방문 여부를 기록하는 배열

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        graph = new int[n][m];
        virusList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 2) virusList.add(new Point(i, j));
            }
        }
        sol(); // 문제 해결을 위한 주 함수 호출
        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
    }

    private void sol() {
        combination(0); // 모든 벽 조합을 시도하는 함수 호출
    }

    // 벽을 설치하는 모든 조합을 시도
    private void combination(int k) {
        if (k == 3) {
            bfs(); // 바이러스 확산을 시뮬레이션하는 함수
            ans = Math.max(ans, countSafe()); // 안전 영역의 최대 크기를 갱신
            return;
        }

        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[0].length; j++) {
                if (graph[i][j] == 0) {
                    graph[i][j] = 1;
                    combination(k + 1);
                    graph[i][j] = 0;
                }
            }
        }
    }

    // BFS를 이용하여 바이러스 확산 시뮬레이션
    private void bfs() {
        Queue<Point> queue = new ArrayDeque<>();
        visited = new boolean[graph.length][graph[0].length];
        for (Point v : virusList) {
            queue.offer(new Point(v.x, v.y));
            visited[v.x][v.y] = true;
        }
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            for (int d = 0; d < direction.length; d++) {
                int nx = p.x + direction[d][0];
                int ny = p.y + direction[d][1];

                if (checkStatus(nx, ny)) {
                    visited[nx][ny] = true;
                    queue.offer(new Point(nx, ny));
                }
            }
        }
    }

    // 지도 내부 위치와 빈 칸인지 확인
    private boolean checkStatus(int nx, int ny) {
        return 0 <= nx && nx < graph.length && 0 <= ny && ny < graph[0].length && !visited[nx][ny] && graph[nx][ny] == 0;
    }

    // 안전 영역의 크기를 계산
    private int countSafe() {
        int count = 0;
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[0].length; j++) {
                if (graph[i][j] == 0 && !visited[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }

    class Point {
        int x, y;

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

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N^2×(N×M))이다. 여기서 N×M은 그리드의 크기이며, 벽을 세우는 모든 조합과 그 각각에 대한 BFS 실행이 포함된다.

느낀점

이 문제는 그래프 탐색과 조합을 통한 시뮬레이션 문제로, BFS를 사용하여 효율적으로 문제를 해결할 수 있었다. 문제의 조건에 맞게 최적의 결과를 도출하기 위해 다양한 시나리오를 고려하는 것이 중요함을 깨달았다. 이러한 문제 해결 기법은 향후 유사한 문제에도 적용할 것 같다.