[백준] code.plus(BFS 알고리즘,JAVA)9376번, 탈옥

문제 링크

9376번: 탈옥

---

주의사항

• 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. 문을 한 번 열면 계속 열려있다.

2. # = 문, . = 빈 공간, * = 막혀있는 공간, $ = 죄수 위치으로 나뉘어진다.

3. 문을 최소로 열면서 죄수 둘다 밖으로 나갈 수 있는 개수를 결과로 출력한다.

4. 상근이가 밖에서 문을 열어주면서 들어올 수 있다.(Why? 상근이는 밖에서 마음대로 움직일 수 있기 때문이다.)

 

이 문제를 처음 접근할 때에는 문제를 자세히 읽지 않아서 두 죄수가 문을 여는 것에만 집중하였습니다.

 

여러가지 시도를 해보다가 검색을 통해서 알아보았을 때 상근이가 밖에서 문을 열어줄 수 있다는 사실을 알게되었습니다.

 

 

죄수1, 죄수2, 상근이가 BFS탐색으로 감옥을 이동하며 문을 연 횟수를 저장하였습니다.

 

이후 각 감옥의 문을 연 횟수의 합을 이용해서 최소값을 구합니다.

 

최소값을 구할 때

 

공간이 '#' 문일 때문을 연 횟수의 합 - 2를 진행해주셔야 합니다.

 

Why?

해당 칸은 죄수1, 죄수2, 상근이가 모두 문을 열었을 때의 합으로써 문을 연 횟수가 2번 중복되기 때문에 -2를 진행합니다..

 

예제입력 1.

 

TC1.

※상근이가 이동할 수 있는 바깥 공간도 배열로 표현하였습니다.

.	.	.	.	.	.	.	.	.	.	.
.	*	*	*	*	#	*	*	*	*	.
.	*	.	.	#	.	#	.	.	*	.
.	*	*	*	*	.	*	*	*	*	.
.	*	$	.	#	.	#	.	$	*	.
.	*	*	*	*	*	*	*	*	*	.
.	.	.	.	.	.	.	.	.	.	.

 

죄수1의 이동 BFS 탐색 시작!

3	3	3	3	3	3	3	3	3	3	3
3	*	*	*	*	3	*	*	*	*	3
3	*	2	2	2	1	2	2	2	*	3
3	*	*	*	*	1	*	*	*	*	3
3	*	0	0	1	1	2	2	2	*	3
3	*	*	*	*	*	*	*	*	*	3
3	3	3	3	3	3	3	3	3	3	3

 

죄수2의 이동 BFS 탐색 시작!

3	3	3	3	3	3	3	3	3	3	3
3	*	*	*	*	3	*	*	*	*	3
3	*	2	2	2	1	2	2	2	*	3
3	*	*	*	*	1	*	*	*	*	3
3	*	2	2	2	1	1	0	0	*	3
3	*	*	*	*	*	*	*	*	*	3
3	3	3	3	3	3	3	3	3	3	3

 

상근(0, 0)이 이동 BFS 탐색 시작!

※저는 상근이의 초기 위치를 바깥쪽 (0, 0)으로 잡았습니다.

※상근이의 위치는 바깥쪽 어느 위치든 상관이 없습니다.

0	0	0	0	0	0	0	0	0	0	0
0	*	*	*	*	1	*	*	*	*	0
0	*	2	2	2	1	2	2	2	*	0
0	*	*	*	*	1	*	*	*	*	0
0	*	2	2	2	1	2	2	2	*	0
0	*	*	*	*	*	*	*	*	*	0
0	0	0	0	0	0	0	0	0	0	0

 

각 문을 연 횟수의 합을 구하기!

 

6	6	6	6	6	6	6	6	6	6	6
6	*	*	*	*	5	*	*	*	*	6
6	*	6	6	4	3	4	6	6	*	6
6	*	*	*	*	3	*	*	*	*	6
6	*	4	4	3	3	3	4	4	*	6
6	*	*	*	*	*	*	*	*	*	6
6	6	6	6	6	6	6	6	6	6	6

 

 

최소값 3을 결과로 출력합니다.

 

※(1, 5)의 '#'(문)에 해당하는 값의 합을 살펴보면 : 3 + 3 + 1 = 7

※문을 연 횟수가 2번 중복되기 때문에 7 - 2 = 5가 저장됩니다!

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 감옥에 대한 정보를 저장하였습니다.
• 상근, 죄수1, 죄수2에 대하여 이동할 수 있는 칸에 대한 문을 연 최소 횟수를 구하는 bfs함수를 실행하였습니다.
• BFS탐색으로 얻은 각 문을 연 최소 횟수들의 합으로 문을 연 최소값을 구하는 minDoor함수를 실행하였습니다.
• 최소값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs는 시작 위치에서 이동할 수 있는 칸에 문을 연 최소 횟수를 다익스트라 BFS탐색하는 함수입니다.
• minDoor는 각 문을 연 횟수의 합을 이용해서 최소값을 구하는 함수입니다.
• minDoor에서 합을 구할 때 '#'인 경우 문을 연 횟수가 2번 중복되어 -2을 진행합니다.

 

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

public class Main {
	//BFS탐색에 PriorityQueue에 사용될 클래스
    static class position implements Comparable<position>{
        int x,y, count;
        public position(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;	//문을 연 횟수
        }
        //문을 연 횟수 기준 오름차순 정렬
        @Override
        public int compareTo(position o) {
            return this.count - o.count;
        }
    }
    static char[][] map;	//감옥 정보 저장 배열
    static ArrayList<position> prisoner;	//죄수 좌표 저장 리스트
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x값 변경
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y값 변경
    static boolean[][] visited;		//감옥 공간 방문 배열
    //죄수1,죄수2,상근이 문을 연 횟수 저장 배열
    static int[][] prisonOne, prisonTwo, prisonThree;	
    public static 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;
        int T = Integer.parseInt(br.readLine());
        //감옥 및 죄수 관련 정보 저장
        for(int i=0;i<T;i++){
            st = new StringTokenizer(br.readLine()," ");
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            prisoner = new ArrayList<>();
            map = new char[h+2][w+2];
            prisoner.add(new position(0, 0, 0));
            for(int j=0;j<h;j++){
                String str = br.readLine();
                for(int s=0;s<w;s++){
                    map[j+1][s+1] = str.charAt(s);
                    if(map[j+1][s+1]=='$'){
                        prisoner.add(new position(s+1,j+1,0));
                    }
                }
            }

            prisonOne = bfs(prisoner.get(0), h, w);	//상근이 BFS탐색
            prisonTwo = bfs(prisoner.get(1), h, w); //죄수1 BFS탐색
            prisonThree = bfs(prisoner.get(2), h, w);	//죄수2 BFS탐색
            bw.write(minDoor(h, w) + "\n");	//문을 연 최소값 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다익스트라 BFS탐색으로 이동가능한 공간에 최소 문을 연 횟수를 구하는 함수
    static int[][] bfs(position p, int h, int w){
        PriorityQueue<position> pq = new PriorityQueue<>();
        visited = new boolean[h+2][w+2];
        int[][] result = new int[h+2][w+2];	//문을 여는 횟수를 저장하는 배열
        visited[p.y][p.x] = true;
        pq.add(p);
        while(!pq.isEmpty()){
            position cur = pq.poll();
            int x = cur.x;
            int y = cur.y;
            int count = cur.count;
            result[y][x] = count;
            //상하좌우 인접한 공간 확인
            for(int i=0;i<4;i++){
                int tempX = x + dx[i];
                int tempY = y + dy[i];
                if(tempX>=0 && tempY>=0 && tempX<w+2 && tempY<h+2 && !visited[tempY][tempX]){
                    if(map[tempY][tempX] != '*'){
                        if(map[tempY][tempX] == '#'){	//인접한 칸이 벽일 때
                            pq.add(new position(tempX,tempY,count+1));
                        } else		//인접한 칸이 빈 공간일 때
                            pq.add(new position(tempX,tempY,count));
                        visited[tempY][tempX] = true;
                    }
                }
            }
        }
        return result;
    }
    //상근, 죄수1, 죄수2에 문을 연 횟수를 통해서 최소값을 구하는 함수
    static int minDoor(int h, int w){
        int result = Integer.MAX_VALUE;
        for(int i=1;i<h+1;i++){
            for(int j=1;j<w+1;j++){
                if(map[i][j] == '*')	//막혀있는 공간일 때
                    continue;
                //문을 연 횟수 합 구하기
                int sum = prisonOne[i][j] + prisonTwo[i][j] + prisonThree[i][j];
                if(map[i][j] == '#')	//벽일 때
                    sum-=2;		//2번 중복되어 문을 연 값 빼기
                /*
                최소값을 구할 때 방문확인을 하는 이유는 
                해당 칸이 '*'으로 둘러싸여 있으면 방문하지 못하지만 문을 연 횟수는
                0이기 때문에 최소값이 될 수 있는 것을 방지하기 위함입니다.
                */
                if(result > sum && visited[i][j]){
                    result = sum;
                }
            }
        }
        return result;	//최소값 반환
    }
}