백준 - 연구소

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

문제 출처 :https://www.acmicpc.net/problem/14502

 

[문제 설명]

벽을 세개 추가하여 바이러스가 가장 적게 퍼지게 만든다.

이 때, 안전한 영역의 크기는?

 

[접근 방법]

완전탐색과 그래프탐색으로 접근했다.

 

맵에 벽을 추가할 수 있는 경우의 수, 벽을 추가한 맵이 만들어지면 거기서 그래프 탐색을 통해 바이러스를 전파시킨다.

전체 지도 크기에서 바이러스가 퍼진 방과 벽의 개수를 빼면 안전한 영역이 나온다.

 

시간복잡도는 완전탐색하는데

조합 : (N*M)C(3)

=> (N*M)*(N*(M-1))*(N*(M-2))/(3*2*1)

N은 최대 8 M도 최대 8이므로 64*63*62/(3*2*1) = > 41664

완전탐색에만 O(N^3M^3)이 든다.

 

또한 그래프를 탐색하는 시간은 바이러스가 주변 4개 방향으로 바이러스의 개수만큼 돌기 때문에

NM(노드의 개수)+4NM(간선의 개수)이 되는 듯하다.

 

완전탐색을 하고 모든 경우에  그래프 탐색을 해야하므로 두 시간 복잡도를 곱한 게 최종 시간 복잡도가 됩니다.

O(N^4*M^4)

 

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

public class Main {
    static int cntOfSafePlaces = 0;
    static int cntOfTotalBlock = 3;
    static int[][] map;
    static List<int[]> locationOfViruses;
    static boolean[][] isVisited;
    static int[][] directions = {{-1,0},{0,1},{1,0},{0,-1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int row = Integer.parseInt(st.nextToken());
        int column = Integer.parseInt(st.nextToken());
        map = new int[row][column];
        locationOfViruses = new LinkedList<>();

        for (int idxOfRow = 0; idxOfRow < row; idxOfRow++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int idxOfColumn = 0; idxOfColumn < column; idxOfColumn++) {
                int state = Integer.parseInt(st.nextToken());
                map[idxOfRow][idxOfColumn] = state;

                if (state == 2) {
                    locationOfViruses.add(new int[]{idxOfRow,idxOfColumn});
                } else if (state == 1){
                    cntOfTotalBlock++;
                }
            }
        }

        setBlock(0, map,0,0);
        System.out.println(cntOfSafePlaces);
    }

    private static void setBlock(int cntOfCurrentBlock, int[][] map, int row, int column){
        if (cntOfCurrentBlock == 3) {
            isVisited = new boolean[map.length][map[0].length];
            int sumOfViruses = getInfectedArea(locationOfViruses, map);
            cntOfSafePlaces = Math.max(map.length*map[0].length-(sumOfViruses+cntOfTotalBlock),cntOfSafePlaces);
            return;
        } else if (column == map[0].length) {
            row++;
            column = 0;
            if (row > map.length - 1) {
                return;
            }
        } else if (map.length-1 < row || map[0].length-1 < column) {
            return;
        }

        if (map[row][column] == 0) {
            map[row][column] = 1;       // 벽 세우기
            setBlock(cntOfCurrentBlock+1, map, row, column+1);
            map[row][column] = 0;
            setBlock(cntOfCurrentBlock, map, row, column+1);
        } else {
            setBlock(cntOfCurrentBlock, map, row, column+1);
        }
    }

    private static int getInfectedArea(List<int[]> locationOfViruses, int[][] map) {
        int cntOfViruses = 0;
        Queue<int[]> q = new LinkedList<>();
        for (int[] locationOfVirus : locationOfViruses) {
            if (isVisited[locationOfVirus[0]][locationOfVirus[1]]) {
                continue;
            }

            q.offer(locationOfVirus);
            while (!q.isEmpty()) {
                int[] currentPosition = q.poll();
                if (isVisited[currentPosition[0]][currentPosition[1]]) {
                    continue;
                }
                if (map[currentPosition[0]][currentPosition[1]] != 1) {
                    if (!isVisited[currentPosition[0]][currentPosition[1]]) {
                        cntOfViruses++;
                    }
                }
                isVisited[currentPosition[0]][currentPosition[1]] = true;

                for (int i = 0; i < directions.length; i++) {
                    int[] nextPosition = {currentPosition[0]+directions[i][0], currentPosition[1]+directions[i][1]};
                    if (0 <= nextPosition[0] && nextPosition[0] <= map.length-1 && 0 <= nextPosition[1] && nextPosition[1] <= map[0].length-1) {
                        if (isVisited[nextPosition[0]][nextPosition[1]] || map[nextPosition[0]][nextPosition[1]] == 1) {
                            isVisited[nextPosition[0]][nextPosition[1]] = true;
                            continue;
                        }
                        q.offer(new int[]{nextPosition[0], nextPosition[1]});
                    }
                }
            }
        }

        return cntOfViruses;
    }
}

 

 

보완이 많이 필요해보이는 코드 같다.

그래도 일단 골드를 풀었다는 점에서, 위안이 생긴다.

사실 시간을 엄청 많이 투자했기 때문에 아직 많이 모자라다.

완전탐색의 경우, 바로 완벽하게 짜는 걸 성공했지만, 그래프 탐색에서 또 헤멨다.

내일도 그래프 탐색과 구현 문제를 잔뜩 풀어야 겠다.