[백준] code.plus(BFS 알고리즘,JAVA)17142번, 연구소 3

문제 링크

17142번: 연구소 3

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. M개의 바이러스에서 모든 빈 칸이 바이러스로 감염되는 최소 요일을 결과로 출력합니다.

2. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치

3. 바이러스는 M개를 놓을 수 있습니다.

 

알고리즘 진행 순서.

 

1. 입력되는 연구소의 정보에서 바이러스의 위치를 저장합니다.

 

2. 모든 바이러스에서 M개의 바이러스를 선택합니다.

 

3. 선택한 바이러스에 대하여 BFS탐색으로 문제에 목표에 만족하는 요일을 구합니다.

 

4. 모든 바이러스의 경우에 소요되는 요일에 최소 값을 결과로 출력합니다.

 

 

예제입력 1.

2	0	0	0	1	1	0
0	0	1	0	1	2	0
0	1	1	0	1	0	0
0	1	0	0	0	0	0
0	0	0	2	0	1	1
0	1	0	0	0	0	0
2	1	0	0	0	0	2

 

1. 입력되는 연구소의 정보에서 바이러스의 위치를 저장합니다.

 

바이러스 위치 : (0, 0) ,(1, 5), (4, 3), (6, 0), (6, 6)

 

 

2. 모든 바이러스에서 M개의 바이러스를 선택합니다.

 

M = 3

 

바이러스 선택!

 

(0, 0), (1, 5), (4, 3)

(0, 0), (1, 5), (6, 0)

......

(4, 3), (6, 0), (6, 6)

 

3. 선택한 바이러스에 대하여 BFS탐색으로 문제에 목표에 만족하는 요일을 구합니다.

 

'-'  = 벽, 0 = 바이러스 놓인 위치, 1~...  = 바이러스 퍼진 시간

 

(0, 0), (1, 5), (4, 3)

0	1	2	3	-	-	2
1	2	-	3	-	0	1
2	-	-	2	-	1	2
3	-	2	1	2	2	3
3	2	1	0	1	-	-
4	-	2	1	2	3	4
5	-	3	2	3	4	5

소요 요일 : 5일

 

(0, 0), (1, 5), (6, 0)

0	1	2	3	-	-	2
1	2	-	4	-	0	1
2	-	-	5	-	1	2
3	-	5	4	3	2	3
2	3	4	5	4	-	-
1	-	5	6	5	6	7
0	-	6	7	6	7	8

소요 요일 : 8일

 

....

 

(4, 3), (6, 0), (6, 6)

6	6	5	4	-	-	7
5	6	-	3	-	5	6
4	-	-	2	-	4	5
3	-	2	1	2	3	4
2	2	1	0	1	-	-
1	-	2	1	2	2	1
0	-	3	2	2	1	0

소요 요일 : 7일

 

4. 모든 바이러스의 경우에 소요되는 요일에 최소 값을 결과로 출력합니다.

 

최소 요일 5을 결과로 출력한다.

 

 

※ 유사한 문제와 차이점

17141번: 연구소 2

차이점

 

연구소 2 : 선택되지 않는 바이러스 칸을 빈 칸으로 처리하였습니다.

 

연구소 3 : 선택되지 않는 바이러스 칸을 빈 칸으로 처리하지 않고 비활성 바이러스 상태로 표현하였습니다.(빈 칸 X)

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 연구소에 대한 정보를 저장하였습니다.
• 연구소에 대한 정보를 저장할 때 바이러스의 위치도 저장하였습니다.
• search함수를 통해서 M개의 바이러스를 선택하였습니다.
• M개의 선택된 바이러스를 기준으로 bfs함수를 실행하여 해당 바이러스가 퍼지는 요일을 구하였습니다.
• 바이러스가 모두 퍼지지 않으면 -1, 모두 퍼지면 최소 요일을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search는 재귀를 통해서 모든 바이러스 중 M개를 선택하는 경우를 구해서 bfs함수를 실행하였습니다.
• bfs은 M개 선택된 바이러스 위치 기준 BFS탐색으로 연구소에 모두 퍼지는 요일을 구하였습니다.
• inLaboratory은 바이러스가 이동한 칸이 연구소에 존재하는 칸인지 확인합니다.
• laboratoryCheck은 모든 바이러스가 연구소에 퍼졌는지 확인합니다.

 

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

public class Main {
    //연구소 위치 관련 클래스
    static class position{
        int x, y;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N,M, answer = Integer.MAX_VALUE;
    static int[][] laboratory;	//연구소 정보 저장 배열
    static position[] route;	//M개 선택한 바이러스 저장 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x 변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y 변경값
    //바이러스 놓을 수 있는 위치 저장 리스트
    static ArrayList<position> virus = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        laboratory = new int[N][N];
        //1. 입력되는 연구소의 정보에서 바이러스의 위치를 저장합니다.
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<N;j++) {
                laboratory[i][j] = Integer.parseInt(st.nextToken());
                if(laboratory[i][j]==2)
                    virus.add(new position(j,i));
            }
        }
        route = new position[M];
        //2. 모든 바이러스에서 M개의 바이러스를 선택합니다.
        search(0, 0);
        //4. 모든 바이러스의 경우에 소요되는 요일에 최소 값을 결과로 출력합니다.
        if(answer == Integer.MAX_VALUE)	//모든 칸 바이러스 감염 불가능할 때
            bw.write("-1");
        else
            bw.write(answer + "");
        bw.flush();
        bw.close();
        br.close();
    }
    //바이러스 놓일 수 있는 위치 M개 선택하는 함수
    static void search(int count, int start){
        if(count == M){
            //3. 선택한 바이러스에 대하여 BFS탐색으로 문제에 목표에 만족하는 요일을 구합니다.
            bfs();
            return;
        }
        for(int i=start;i<virus.size();i++){
            route[count] = virus.get(i);
            search(count+1, i + 1);
        }
    }
    //M개 선택한 바이러스 위치 기준 BFS탐색으로 모두 감염되는 요일 구하는 함수
    static void bfs(){
        Queue<position> queue = new LinkedList<>();
        int result = 0;
        boolean[][] visited = new boolean[N][N];
        //M개 선택한 바이러스 위치 Queue 저장
        for(int i=0;i<M;i++){
            queue.add(new position(route[i].x, route[i].y));
            visited[route[i].y][route[i].x] = true;
        }
        while(!queue.isEmpty()){
            if(result >= answer)	//최소 요일보다 더 커질 경우 탐색 종료
                return;
            if(laboratoryCheck(visited)){	//모든 빈 칸 바이러스 감염시
                answer = Math.min(answer, result);
                return;
            }
            int size = queue.size();
            //바이러스 인접한 칸 탐색
            for(int i=0;i<size;i++){
                position cur = queue.poll();
                for(int j=0;j<4;j++){
                    int tempX = cur.x + dx[j];
                    int tempY = cur.y + dy[j];
                    if(inLaboratory(tempX,tempY) && !visited[tempY][tempX] && laboratory[tempY][tempX]!=1){
                        visited[tempY][tempX] = true;
                        queue.add(new position(tempX, tempY));
                    }
                }
            }
            result++;
        }
    }
    //모든 빈 칸이 바이러스에 감염되었는지 확인하는 함수
    static boolean laboratoryCheck(boolean[][] visited){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(laboratory[i][j]==0 && !visited[i][j])
                    return false;
            }
        }
        return true;
    }
    //이동하는 좌표가 연구소 안에 존재하는지 확인하는 함수
    static boolean inLaboratory(int x, int y){
        if(x>=0 && y>=0 && x<N && y<N)
            return true;
        return false;
    }
}