[백준] 연구소 : 14502 : Java - 그래프 탐색 (G4)

1.  📄 문제

14502번: 연구소

 

- 반드시 3개의 벽을 세워서 확보할 수 있는 안전 구역의 최댓값을 구하기

 

---

2. 🤔 어떻게 풀까?

문제를 처음 봤을 때 대체 어떠한 방법으로 벽을 세울 위치를 정해야될지 난감했다. 바이러스를 중심으로 한다해도 어렵고, 벽을 중심으로 해도 어렵고.. 모르겠다가 넉넉한 시간과 작은 N과 M의 개수를 보고 완전 탐색을 생각했다.

 

그후 과연 시간 조건을 충족할 수 있을지 계산을 해보았고 아주 넉넉했다. 그래서 벽을 세울 수 있는 모든 경우의 수로 벽을 세우고, BFS 탐색을 진행하여 안전 구역의 최댓값을 찾기로 하였다.

 

 

3. 💡 로직

1. 벽세우기

제일 먼저 고민스러웠던 점은 어떻게 3개의 벽을 선정하느냐 였다. 고민하다가 그냥 3중 포문을 쓰기로 하였다.

우선 `i`, `j`, `k` 로 빈 공간 중에서 세 개의 좌표를 정한다. 그 후 기존 맵을 클론하여  임시맵인 `tempMap`을 생성하고 3개의 좌표를 벽으로 바꾼다. 

// 벽을 세울 3개의 좌표 선택
for(int i = 0; i< emptyPoints.size(); i++){
    for(int j = i+1; j< emptyPoints.size(); j++){
        for(int k = j+1; k< emptyPoints.size(); k++){
            // 2차원 배열은 얕은 복사가 안된다
            int[][] tempMap = Arrays.copyOf(map, map.length);
            for (int p = 0; p < map.length; p++) {
                tempMap[p] = Arrays.copyOf(map[p], map[p].length);
            }
            // 3개의 빈 곳을 벽으로 변경
            chageThreeEmptyZoneToWall(tempMap, i, j, k);
            
            }
            
            
private void chageThreeEmptyZoneToWall(int[][] tempMap, int i, int j, int k) {
        tempMap[emptyPoints.get(i).row][emptyPoints.get(i).col] = WALL;
        tempMap[emptyPoints.get(j).row][emptyPoints.get(j).col] = WALL;
        tempMap[emptyPoints.get(k).row][emptyPoints.get(k).col] = WALL;
    }

 

 

2. 안전 구역 수 알아내기

바뀐 맵으로 바이러스 위치를 시작으로 BFS 탐색을 진행한다. 오염된 지역의 개수를 알아내기 위함이다.  바이러스 위치를 시작으로 할 때 BFS탐색으로 탐색되면 오염된 지역이다. 모든 바이러스 위치를 기준으로 탐색을 진행하고 `BFS()`는 바이러스 위치가 포함된 오염된 지역의 수를 리턴한다. 

 

최종적으로 안전 구역의 수는 전체 구역 수 - (벽의 개수 + 오염된 지역 수) - 임의로 세운 벽의 수(3) 이다. 이러한 방식으로 모든 벽을 세울 수 있는 경우마다 안전 구역 개수를 알아내어 최대값을 최종 답으로 출력한다.

private int findSafeZoneCount(boolean[][] isVisited, int[][] tempMap) {
        int contaminatedCount = 0;

        for(Point currentPos : virusPoints){
            if(!isVisited[currentPos.row][currentPos.col]){
                // BFS 탐색 진행
                isVisited[currentPos.row][currentPos.col] = true;
                contaminatedCount += BFS(currentPos, isVisited, tempMap);
            }
        }
        return N*M - (wallSize + contaminatedCount) -3;
    }

 

 

3.  🖥️ 전체 코드 - Java

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

public class Main{
    final static int EMPTY = 0;
    final static int WALL = 1;
    final static int VIRUS = 2;

    static BufferedReader br;
    static BufferedWriter bw;

    int N;
    int M;
    int wallSize = 0;
    int ans = 0;
    int [][] map;
    List<Point> emptyPoints;
    List<Point> virusPoints;

    public Main(){
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    public void run() throws Exception{
        input();
        solution();
        output();
    }

    public void input() throws Exception{
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        map = new int[N][M];
        emptyPoints = new ArrayList<>();
        virusPoints = new ArrayList<>();

        // 맵 입력 받기
        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());

                if(map[i][j] == EMPTY){
                    emptyPoints.add(new Point(i,j));
                }
                else if(map[i][j] == WALL){
                    wallSize++;
                }
                else if(map[i][j] == VIRUS){
                    virusPoints.add(new Point(i,j));
                }
            }
        }
    }

    public void solution(){
        // 벽을 세울 3개의 좌표 선택
        for(int i = 0; i< emptyPoints.size(); i++){
            for(int j = i+1; j< emptyPoints.size(); j++){
                for(int k = j+1; k< emptyPoints.size(); k++){
                    // 2차원 배열은 얕은 복사가 안된다
                    int[][] tempMap = Arrays.copyOf(map, map.length);
                    for (int p = 0; p < map.length; p++) {
                        tempMap[p] = Arrays.copyOf(map[p], map[p].length);
                    }
                    // 3개의 빈 곳을 벽으로 변경
                    chageThreeEmptyZoneToWall(tempMap, i, j, k);

                    boolean [][] isVisited = new boolean[N][M];
                    // 벽을 세웠을 때 안전 구역 수 찾기
                    ans = Math.max(ans, findSafeZoneCount(isVisited, tempMap));
                }
            }
        }
    }

    private void chageThreeEmptyZoneToWall(int[][] tempMap, int i, int j, int k) {
        tempMap[emptyPoints.get(i).row][emptyPoints.get(i).col] = WALL;
        tempMap[emptyPoints.get(j).row][emptyPoints.get(j).col] = WALL;
        tempMap[emptyPoints.get(k).row][emptyPoints.get(k).col] = WALL;
    }

    private int findSafeZoneCount(boolean[][] isVisited, int[][] tempMap) {
        int contaminatedCount = 0;

        for(Point currentPos : virusPoints){
            if(!isVisited[currentPos.row][currentPos.col]){
                // BFS 탐색 진행
                isVisited[currentPos.row][currentPos.col] = true;
                contaminatedCount += BFS(currentPos, isVisited, tempMap);
            }
        }
        return N*M - (wallSize + contaminatedCount) -3;
    }


    private int BFS(Point start, boolean[][] isVisited, int[][] map) {
        int [] dx = {1,0,-1,0};
        int [] dy = {0, -1, 0, 1};
        int count = 1;
        Queue<Point> que = new ArrayDeque<>();
        que.add(start);

        while(!que.isEmpty()){
            Point curPoint = que.poll();
            for(int i=0; i<4; i++){
                int nextRow = curPoint.row + dx[i];
                int nextCol = curPoint.col + dy[i];

                if(isRange(nextRow, nextCol) && !isVisited[nextRow][nextCol]){
                    if(map[nextRow][nextCol] != WALL){
                        que.add(new Point(nextRow,nextCol));
                        isVisited[nextRow][nextCol]= true;
                        count++;
                    }
                }
            }
        }
        return count;
    }

    private boolean isRange(int row, int col){
        if(row<N && row >=0 && col<M && col>=0)
            return true;
        return false;
    }


    public void output() throws Exception{
        bw.write(ans+"\n");
        bw.flush();

        bw.close();
        br.close();
    }

    public static void main(String [] args) throws Exception{

        new Main().run();

    }

    public static class Point{
        int row;
        int col;

        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

}