[백준] 연구소 3 (조합, bfs)

https://www.acmicpc.net/problem/17142

풀이과정

0. 입력을 받을 때 채워야 할 빈칸의 갯수를 저장합니다.

1. 백트래킹을 활용해서 바이러스들의 조합을 선택합니다.

2. 선택된 바이러스들에 대해 bfs를 수행하여 퍼트립니다.

• 바이러스를 퍼트릴 때, 빈칸과 바이러스가 있는 칸에 대해 구분해서 코드를 작성해야 합니다.
• 빈 칸의 경우 0번 풀이과정에서 저장한 목표와 비교하기 위해 cnt값을 증가시켜 줍니다.
• 바이러스의 경우 cnt 값을 증가시키지 않고 방문처리와 bfs큐에 넣는 동작만 수행합니다.

처음에는 swea의 지뢰문제와 헷갈려서 바이러스를 만나면 계속 퍼지도록 구현해서 계속 틀렸습니다 ㅠㅠ

3. 빈 칸을 다 채웠으면 이동한 시간을 return 합니다.

• bfs에서 시간은 계속 커지게 되어, 처음 빈 칸을 다 채운경우가 최단 시간입니다.

4. 이때 빈 칸이 하나도 없는 입력이 주어진 경우에 대해서 예외처리를 해줘야 합니다.

예외처리를 해주지 않으면 정답이 0이 아닌 1이 나오게 됩니다.

 

알게된 점

• list의 remove함수는 인덱스에 대해서 동작하며, 객체에 대해서도 동작합니다.
• 백트래킹을 활용한 조합 구현을 다시 익힐 수 있었습니다.

 

전체코드

package com.mincheolsong;
import java.util.*;
import java.io.*;

public class Main {

    static int N,M;
    static int[][] arr;
    static List<int[]> virus;
    static List<int[]> selected;
    static int goal;
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,1,0,-1};
    static boolean[][] visited;
    static final int INF = (int)1e9;
    static int ans;

    static int[] bfs(List<int[]> list){
        Deque<int[]> q = new ArrayDeque<>();
        visited = new boolean[N][N];
        int cnt = 0;

        for(int i=0;i<list.size();i++){ // 선택한 바이러스들 bfs큐에 넣기
            int[] p = list.get(i);
            q.offer(new int[]{p[0],p[1],0}); // 행,열,시간
            visited[p[0]][p[1]]=true;
        }

        while(!q.isEmpty()){
            int[] c = q.pollFirst();
            int cr = c[0];
            int cc = c[1];
            int sec = c[2];

            for(int d=0;d<4;d++){
                int nr = cr + dr[d];
                int nc = cc + dc[d];
                if(nr<0 || nr>=N) continue;
                if(nc<0 || nc>=N) continue;
                if(arr[nr][nc]==1) continue;

                if(visited[nr][nc]){
                    continue;
                }

                // 바이러스인 경우는 그냥 방문처리 하고 큐에 넣어줌

                if(arr[nr][nc]==0){ // 빈 칸을 방문한 경우 갯수 세기
                    cnt+=1;
                }

                visited[nr][nc]=true;
                q.offer(new int[]{nr,nc,sec+1});

                if(cnt==goal){ // 빈 칸을 다 채웠으면 그 때가 최단시간 이므로 return (bfs의 sec는 계속 증가함)
                    return new int[]{cnt,sec+1};
                }

            }
        }

        return new int[]{-1,-1};
    }


    static void solve(int n,int start){ // 조합
        if(n==M){
            int[] result = bfs(selected); // 선택된 바이러스들에 대해서 bfs

            if(result[0]==goal){ // 빈 칸을 다 채운경우
                ans = Math.min(ans,result[1]); // 최솟값 갱신
            }
            return;
        }

        for(int i=start;i<virus.size();i++){
            selected.add(virus.get(i));
            solve(n+1,i+1);
            selected.remove(selected.size()-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());
        virus = new ArrayList<>();
        selected = new ArrayList<>();
        goal = 0;
        arr = new int[N][N];
        ans = INF;

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                int input = Integer.parseInt(st.nextToken());
                arr[i][j] = input;
                if(arr[i][j]==2){ // 바이러스
                    virus.add(new int[]{i,j});
                }else if(arr[i][j]==0){ // 0인 곳 (채워야 할 빈칸의 갯수 세기)
                    goal+=1;
                }
            }
        }


        if(goal==0){ // 빈칸이 하나도 없는 경우 정답은 0
            ans = 0;
        }else{
            solve(0,0);
        }

        System.out.println(ans==INF?-1:ans);
    }
}