2 분 소요

문제

문제 바로가기

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 비활성 바이러스의 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

접근방법

  1. 바이러스가 있는 위치를 list에 추가한다.
  2. 백트래킹을 통해 활성 바이러스 M개를 선택하는 모든 경우의 수를 탐색한다.
  3. 매번 기존의 map을 copy에 복사한다.
  4. 너비우선탐색을 수행한다.
  5. copy에서 빈 칸이 남아있다면 -1을 반환한다.
  6. 빈 칸이 없다면 바이러스가 퍼진 시간 중 최대값을 구하여 반환한다. 주의해야할 점은 최대값을 구할 때 초기 list에 저장한 바이러스가 위치해있던 칸은 제외한다.
  7. 모든 탐색을 완료한 후 최소 시간을 출력한다.

풀이

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

class Coo {
    int x, y;
    Coo(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int N, M;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static List<Coo> list = new ArrayList<>();
    static List<Coo> virus = new ArrayList<>();
    static int res = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 2) {
                    list.add(new Coo(i, j));
                }
            }
        }

        dfs(0, 0);

        if(res == Integer.MAX_VALUE)
            bw.write(String.valueOf(-1));
        else
            bw.write(String.valueOf(res-3));
        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int depth, int idx) {
        if(depth == M) {
            int value = bfs();
            if(value != -1) {
                res = Math.min(res, value);
            }
            return;
        }
        for(int i = idx; i < list.size(); i++) {
            virus.add(list.get(i));
            dfs(depth+1, i+1);
            virus.remove(virus.size()-1);
        }
    }

    public static int bfs() {
        int[][] copy = new int[N][N];
        for(int i = 0; i < N; i++) {
            copy[i] = map[i].clone();
        }
        Queue<Coo> q = new LinkedList<>();
        for(Coo c : virus) {
            copy[c.x][c.y] = 3;
            q.offer(c);
        }

        while(!q.isEmpty()) {
            Coo tmp = q.poll();
            for(int i = 0; i < 4; i++) {
                int tx = tmp.x + dx[i];
                int ty = tmp.y + dy[i];
                if(tx >= 0 && ty >= 0 && tx < N && ty < N) {
                    if(copy[tx][ty] == 0 || copy[tx][ty] == 2) {
                        copy[tx][ty] = copy[tmp.x][tmp.y] + 1;
                        q.offer(new Coo(tx, ty));
                    }
                }
            }
        }

        int max = 3;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(copy[i][j] == 0)
                    return -1;
                if(map[i][j] != 2) {
                    max = Math.max(max, copy[i][j]);
                }
            }
        }

        return max;
    }
}

댓글남기기

참고