[알고리즘] 백준 14502 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

 

벽을 무조건 3개 세웠을 때 가장 최소의 칸만큼 바이러스가 퍼지는 경우를 구하는 문제이다.

 

입력범위가 매우 작다(80) ,,,// 제발 문제풀기전에 입력 범위 숙지하는 습관좀...

 

입력범위가 작기 때문에 3개의 벽을 세우는 모든 경우에 대하여 구해도 시간초과가 나지 않는다.

 

그러므로 백트래킹을 통해 모든 경우에 대해 3개의 벽을 세우고, depth가 꽉 차면 바이러스를 퍼뜨린다(bfs)

 

즉 이 문제는 dfs + bfs 모두를 사용하여 풀어야한다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

    static int n;
    static int m;

    static int[][] map;

    static int minVirusArea = -1;
    static int wallCount;
    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");

            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) wallCount++;
            }
        }

        buildWall( 0);
        System.out.println(minVirusArea);
    }

    static void buildWall(int count) {
        // 백트래킹으로 벽세우기
        if (count == 3) {
            minVirusArea = Math.max(spreadVirus(), minVirusArea);
            return;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    buildWall(count + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

    static int spreadVirus()  {

        // 바이러스 퍼뜨리기

        Queue<Location> queue = new LinkedList<>();
        int[][] copyMap = new int[n][m]; // 초기 입력을 받은 map을 건들면 안되므로 새로운 map 생성

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                copyMap[i][j] = map[i][j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyMap[i][j] == 2) {
                    queue.add(new Location(i, j, 0));
                }
            }
        }

        while (!queue.isEmpty()) {
            Location current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (copyMap[nx][ny] == 0) {
                        queue.add(new Location(nx, ny, current.value + 1));
                        copyMap[nx][ny] = 2;
                    }
                }
            }
        }

        return getSafeCount(copyMap);
    }

    public static int getSafeCount(int[][] copyMap) {

        // 안전 지역 개수 세기 (벽도 아니고 바이러스도 아닌곳)
        int safeCount = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyMap[i][j] == 0) {
                    safeCount++;
                }
            }
        }

        return safeCount;
    }

    static class Location {
        int x;
        int y;
        int value;

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