백준 17141 (연구소 2) - java

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

17141번: 연구소 2

백트랙킹과 BFS를 사용해야 하는 유형이다. 백트랙킹 문제에서 관건은 함수 호출의 횟수를 최대한으로 줄이는 것 , 그리고 한번 호출될 때 해당 함수의 시간이 적게 걸리도록 하는 것이다. 위 문제는 이러한 작업을 하기 위해 여러 가지 장치를 필요로 한다. 코드로 상세하게 설명하겠다. 

 

import java.io.*;
import java.util.*;
public class Main {

    static int n = 0;
    static int m = 0;
    static int[][] board = new int[51][51]; // 입력 배열
    static boolean[][] visit = new boolean[51][51]; // 백트랙킹 여부 판단 배열
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0}; // 상하좌우 이동
    static point[] virus = new point[11]; // 바이러스의 최대 개수는 10개 
    static LinkedList<point> possible = new LinkedList<>(); // 바이러스가 심어질 수 있는 공간
    static int count = 0; // 유효 공간 (빈 공간)
    static int result = -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());

        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=n;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j]==2) {
                    possible.add(new point(i, j)); // 바이러스가 심어질 수 있는 공간
                    count++; 
                }
                if(board[i][j]==0)
                    count++;
            }
        }
        if(count==m) 
        {
            System.out.println(0);
        }
        else {
            travel(0,0);
            System.out.println(result);
        }
        br.close();
    }
    static int bfs()
    {
        int remain = count - m; // 바이러스를 심을 경우 남은 공간은 빈공간으로 처리해야 한다
        int result = 1;
        Queue<point> q= new LinkedList<>();
        int[][] visit2 = new int[51][51]; // bfs 실행을 위한 방문 배열

        for(int i=1;i<=m;i++)
        {
            q.add(virus[i]); 
            visit2[virus[i].x][virus[i].y]=1; // 백트랙킹을 통해 선별한 바이러스 공간 m개에 대한 선 처리
        }

        while(!q.isEmpty())
        {
            point cur = q.poll();

            if(visit2[cur.x][cur.y]>result)
                result = visit2[cur.x][cur.y];

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

                if(nx>=1&&nx<=n&&ny>=1&&ny<=n)
                {
                    if(visit2[nx][ny]==0&&board[nx][ny]!=1) // 빈공간이고 방문한적 없다면
                    {
                        visit2[nx][ny]=visit2[cur.x][cur.y]+1;
                        q.add(new point(nx,ny));
                        remain = remain-1; // 빈 공간이 하나 줄어든다 (전염)
                    }
                }
            }
        }

        if(remain==0) // 빈공간의 개수가 0이라면 성공적으로 모든 공간에 전염을 시킨 것
        {
            return result-1;
        }
        else{ // 그렇지 않을 경우 문제 조건에 의해 -1 반환
            return -1;
        }
    }

    static void travel(int k,int pos)
    {
        if(k==m) // m개만큼 바이러스를 심을 경우 종료 조건
        {
            int tmp = bfs(); // bfs 수행
            if(result==-1&&tmp>0) // 갱신 작업 (최솟값)
                result =  tmp;
            else if(tmp==-1)
                return;
            else if(result>tmp)
                result = tmp;

            return;
        }
        if(pos<possible.size()) {
            point cur = possible.get(pos);
            if (!visit[cur.x][cur.y]) {
                visit[cur.x][cur.y] = true;
                virus[k + 1] = new point(cur.x, cur.y);
                travel(k + 1, pos + 1); // 가능한 위치에 바이러스를 심은 경우
                visit[cur.x][cur.y] = false;
                virus[k + 1] = null;
                travel(k, pos + 1); // 바이러스를 심지 않은 경우
            }
        }
    }
}
class point
{
    int x;
    int y;

    point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}