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

문제 링크

14502번: 연구소

---

주의사항

• 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. 지도의 0은 빈 칸, 1은 벽, 2는 바이러스입니다.

2. 벽을 무조건 3개를 설치해야 한다.

3. 벽을 3개 설치하고 바이러스가 퍼졌을 때 최대 빈 칸의 개수를 결과로 출력합니다.

 

지도에 벽을 3개 설치하는 모든 경우에서 BFS 탐색을 진행하여 가장 빈 칸이 많은 값을 결과로 출력하였습니다.

 

모든 경우를 구할 때에는 재귀를 통해서 구하였습니다.

 

예제입력 2.

바이러스 위치 저장(1, 5), (2, 5), (3, 5)

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

아래의 표는 벽을 3개 설치했을 때 가장 빈 칸이 많이 나올 때입니다.

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

바이러스 퍼지기 시작!

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

 

빈 칸(0)의 개수 : 9개

 

결과 9를 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 연구실 지도에 대한 정보를 저장하였습니다.
• 벽을 설치하는 모든 경우에서 BFS탐색을 진행해서 빈 칸의 최대 개수를 구하는 search함수를 실행하였습니다.
• 빈 칸의 최대 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀를 통해서 벽이 3개가 설치되었을 경우 bfs 함수를 실행시켜 BFS탐색을 실행하였습니다.
• bfs함수는 바이러스 위치를 기준으로 BFS탐색을 진행하여 바이러스가 퍼지는 것처럼 구현하였습니다.
• cleanCheck함수는 바이러스가 퍼진 이후 빈 칸의 개수를 구하는 함수입니다.

 

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,result = Integer.MIN_VALUE;
    static int[][] laboratory;	//지도 정보 저장 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 X값 변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 Y값 변경값
    static ArrayList<position> virus = new ArrayList<>();	//바이러스 위치 저장 리스트
    static public void  main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        laboratory = new int[N][M];
        //지도 정보 및 바이러스 위치 저장
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++){
                laboratory[i][j] = Integer.parseInt(st.nextToken());
                if(laboratory[i][j]==2)
                    virus.add(new position(j,i));
            }
        }
        search(0,0,0);	//벽을 3개 설치하는 모든 경우에서 BFS 탐색 진행하는 함수 실행
        bw.write(result + "\n");	//빈 칸의 최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //지도에 벽을 3개 설치하는 모든 경우를 구해서 BFS탐색으로 최대 빈 칸의 수를 구하는 함수
    static void search(int x, int y, int count){
        if(count==3){		//벽을 3개 설치했을 때
            result = Math.max(result, bfs());
            return;
        }
        if(y>=N)
            return;

        if(x<M-1){
            if(laboratory[y][x]==0){
                laboratory[y][x] = 1;
                search(x+1, y, count+1);
                laboratory[y][x] = 0;
            }
            search(x+1, y, count);
        }else{
            if(laboratory[y][x] == 0){
                laboratory[y][x] = 1;
                search(0,y+1, count+1);
                laboratory[y][x] = 0;
            }
            search(0,y+1, count);
        }
    }
    //현재 지도에서 바이러스가 퍼지는 것을 진행하는 BFS 함수
    static int bfs(){
        Queue<position> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        for(position temp : virus)		//바이러스 위치 큐에 저장
            queue.add(temp);
        while(!queue.isEmpty()){
            position cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            for(int i=0;i<4;i++){
                int tempX = x + dx[i];
                int tempY = y + dy[i];
                if(tempX>=0 && tempY>=0 && tempX<M && tempY<N){
                    if(laboratory[tempY][tempX]==0 && !visited[tempY][tempX]){
                        visited[tempY][tempX] = true;
                        queue.add(new position(tempX,tempY));
                    }
                }
            }
        }
        return cleanCheck(visited);
    }
    //현재 지도에 빈 칸에 개수를 확인하는 함수
    static int cleanCheck(boolean[][] visited){
        int count = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++) {
                if(laboratory[i][j]==0 && !visited[i][j])
                    count++;
            }
        }
        return count;
    }
}