이번에 풀어본 문제는
백준 17142번 연구소3 입니다.

📕 문제 링크

❗️코드

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

class Virus
{
    int x,y,cnt;

    public Virus(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    public Virus(int x, int y,int cnt)
    {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}
public class Main {
    static int zero_cnt;
    static int answer = Integer.MAX_VALUE;
    static int N,M;
    static int v_size;
    static int [][] map;
    static boolean [][] visited;
    static List<Virus> virus;
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        virus = new ArrayList<>();

        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] > 1)
                {
                    virus.add(new Virus(i,j));
                }
                else if(map[i][j] == 0) zero_cnt++;
            }
        }
        v_size = virus.size();
        comb("",M,0,0);
        if(answer == Integer.MAX_VALUE) answer = -1;
        System.out.print(answer);
    }
    static void comb(String str,int dest,int cnt, int idx)
    {
        if(cnt == dest)
        {
            visited = new boolean[N][N];
            String [] str_arr = str.split(" ");
            Virus [] v_arr = new Virus[dest];
            for(int i = 0; i < dest; ++i)
            {
                v_arr[i] = virus.get(Integer.parseInt(str_arr[i]));
            }
            spread(v_arr);
            return;
        }

        for(int i = idx; i < v_size; ++i)
        {
            comb(str+i+" ",dest,cnt+1,i+1);
        }
    }
    static void spread(Virus [] arr)
    {
        Queue<Virus> q = new LinkedList<>();
        for(Virus v : arr)
        {
            q.add(new Virus(v.x,v.y,0));
            visited[v.x][v.y] = true;
        }

        int tmp_cnt = zero_cnt;
        int time = Integer.MIN_VALUE;
        while(!q.isEmpty())
        {
            Virus cur = q.poll();
            if(tmp_cnt == 0)
            {
                time = Math.max(time,cur.cnt);
                continue;
            }
            for(int idx = 0; idx < 4; ++idx)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if(!isValid(mx,my) || visited[mx][my] || map[mx][my] == 1) continue;
                visited[mx][my] = true;
                if(map[mx][my] == 0) tmp_cnt--;
                q.add(new Virus(mx,my,cur.cnt+1));
            }
        }
        if(time == Integer.MIN_VALUE) return;
        answer = Math.min(time,answer);

    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}

📝 풀이

바이러스를 M개만 활성화 시킨 상태로 퍼뜨렸을 때, 연구소 전체로 전이시킬 수 있는 최단시간을 구하는 문제입니다.
각 경우의 수를 모두 고려하기 위해 조합알고리즘을 구현하였고, 활성화된 바이러스의 위치를 큐에 담아서 전이시켰습니다. 처음 입력에서 0의 갯수를 카운트 해놓고, 빈칸으로 전이 될때마다 카운트값을 감소시켜서 카운트가 0이되는 순간 모든 전이가 완료되었다고 판단했습니다. 배열을 탐색할 필요가 없어 속도면에서 유리할 것이라 생각됩니다.
연구소를 완벽히 전이시킨 경우 중, 가장 최단시간을 answer에 누적하여 최종적으로 가장 작은값을 출력하면 해결됩니다.

📜 후기

조건을 잘 확인하면 그렇게 어려운 문제는 아니었던 것 같습니다.
코딩 테스트를 마치고 조금 급하게 풀다보니 최선의 풀이라고는 생각이 들지 않아서, 다음에 다시 검토해볼 생각입니다.