[백준, Java] 6593번, 상범 빌딩 알고리즘 분류(그래프 탐색, BFS)

문제 링크

6593번: 상범 빌딩

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 빌딩에는 L, R, C의 크기의 3차원으로 이루어져있습니다.

2. 1분 동안에 상, 하, 동, 서, 남, 북으로만 이동이 가능하다.

3. 상범 빌딩에서는 '#'으로 이동할 수 없으며 'S'에서 시작해서 'E'(출구)까지 도착해야한다.

4. 출구에 도착하는 최단 시간을 결과로 출력하고 출구에 도착하지 못하면 Trapped!을 결과로 출력한다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 시작위치('S')를 기준으로 출구('E')까지의 최단 거리를 다익스트라로 탐색합니다.

 

3. 출구에 도착할 때에는 최단 거리, 도착하지 못할 때는 Trapped!을 결과로 출력합니다.

 

 

빌딩 탐색하기

 

상하동서남북으로 탐색할 때 l, r, c의 변경값

 

상하동서남북 순

 

dl = {-1, 1 ,0, 0, 0, 0}

 

dr = {0, 0, -1, 1, 0, 0}

 

dc = {0, 0, 0, 0, -1, 1}

 

'S'을 시작으로 'E'에 갈 때까지 다익스트라 탐색을 진행!

 

예제입력 1.

1. 입력된 정보를 저장합니다.

※ 1번째 테스트케이스가 진행되는 과정만 보여드리겠습니다.

 

L : 3

R : 4

C : 5

 

1층

S	.	.	.	.
.	#	#	#	.
.	#	#	.	.
#	#	#	.	#

 

2층

#	#	#	#	#
#	#	#	#	#
#	#	#	#	#
#	#	.	.	.

 

3층

#	#	#	#	#
#	#	#	#	#
#	.	#	#	#
#	#	#	#	E

 

2. 시작위치('S')를 기준으로 출구('E')까지의 최단 거리를 다익스트라로 탐색합니다.

 

1분동안 이동!

1층

S	O	.	.	.
O	#	#	#	.
.	#	#	.	.
#	#	#	.	#

 

2층

#	#	#	#	#
#	#	#	#	#
#	#	#	#	#
#	#	.	.	.

 

3층

#	#	#	#	#
#	#	#	#	#
#	.	#	#	#
#	#	#	#	E

 

2분동안 이동!

1층

S	O	O	.	.
O	#	#	#	.
O	#	#	.	.
#	#	#	.	#

 

2층

#	#	#	#	#
#	#	#	#	#
#	#	#	#	#
#	#	.	.	.

 

3층

#	#	#	#	#
#	#	#	#	#
#	.	#	#	#
#	#	#	#	E

 

3분동안 이동!

1층

S	O	O	O	.
O	#	#	#	.
O	#	#	.	.
#	#	#	.	#

 

2층

#	#	#	#	#
#	#	#	#	#
#	#	#	#	#
#	#	.	.	.

 

3층

#	#	#	#	#
#	#	#	#	#
#	.	#	#	#
#	#	#	#	E

....

10분동안 이동!

1층

S	O	O	O	O
O	#	#	#	O
O	#	#	O	O
#	#	#	O	#

 

2층

#	#	#	#	#
#	#	#	#	#
#	#	#	#	#
#	#	O	O	O

 

3층

#	#	#	#	#
#	#	#	#	#
#	.	#	#	#
#	#	#	#	E

 

11분동안 이동!

1층

S	O	O	O	O
O	#	#	#	O
O	#	#	O	O
#	#	#	O	#

 

2층

#	#	#	#	#
#	#	#	#	#
#	#	#	#	#
#	#	O	O	O

 

3층

#	#	#	#	#
#	#	#	#	#
#	.	#	#	#
#	#	#	#	E

 

 

 

 

 

3. 출구에 도착할 때에는 최단 거리, 도착하지 못할 때는 Trapped!을 결과로 출력합니다.

 

 

출구('E') 11분에 최초로 도착!!

 

Escaped in 11 minute(s). 을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 빌딩의 크기 L, R, C을 저장합니다.
• bfs 함수를 이용하여 시작위치에서 출구까지의 최단 거리를 탐색합니다.
• 출구에 도착하면 최단거리, 못하면 Trapped!를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• bfs함수는 BFS(다익스트라)으로 상하동서남북 출구까지의 최단 거리를 탐색합니다.
• inSpace함수는 (l, r, c)가 빌딩에 존재하는지 확인하는 함수입니다.

 

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    //빌딩 현재 위치 및 이동한 시간 관련 클래스
    static class Info implements Comparable<Info>{
        int l, r, c, val;
        public Info(int l, int r, int c, int val){
            this.l = l;
            this.r = r;
            this.c = c;
            this.val = val;
        }

        //시간 관련 오름차순 정렬
        @Override
        public int compareTo(Info o) {
            return this.val - o.val;
        }
    }
    static char[][][] building;
    static int[] dl = {-1, 1, 0, 0, 0, 0};	//상하동서남북 l 변경값
    static int[] dr = {0, 0, -1, 1, 0, 0};	//상하동서남북 r 변경값
    static int[] dc = {0, 0, 0, 0, -1, 1};	//상하동성남북 c 변경값
    static int L,R,C, sl, sr, sc;
    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;
        StringBuilder sb = new StringBuilder();
        //각 테스트케이스 탐색 진행
        while(true){
            //입력값 저장
            st = new StringTokenizer(br.readLine()," ");
            L = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            //테스트 종료
            if(L == 0 && R == 0 && C == 0)
                break;
            building = new char[L][R][C];
            //빌딩 정보 저장
            for(int i=0;i<L;i++){
                for(int j=0;j<R;j++){
                    String str = br.readLine();
                    for(int s=0;s<C;s++){
                        building[i][j][s] = str.charAt(s);
                        //시작위치 저장
                        if(building[i][j][s] == 'S'){
                            sl = i;
                            sr = j;
                            sc = s;
                        }
                    }
                }
                br.readLine();
            }
            //시작위치 기준 BFS(다익스트라)탐색 시작!
            int min = bfs(sl, sr, sc);
            //출구에 도착하지 못할 때
            if(min == -1)
                sb.append("Trapped!\n");
            else	//출구에 도착했을 때 최단 거리 StringBuilder 저장
                sb.append("Escaped in ").append(min).append(" minute(s).\n");
        }
        bw.write(sb.toString());		//결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //시작 위치 기준 BFS(다익스트라)를 통한 최단 거리 탐색하는 함수
    static int bfs(int sl, int sr, int sc){
        //다익스트라를 위한 Priority Queue
        PriorityQueue<Info> pq = new PriorityQueue<Info>();
        pq.add(new Info(sl, sr, sc, 0));	//시작 위치 저장
        boolean[][][] visited = new boolean[L][R][C];
        visited[sl][sr][sc] = true;	//시작위치 방문 확인
        //다익스트라 탐색 시작
        while(!pq.isEmpty()){
            Info cur = pq.poll();
            //가장 먼저 출구 도착시
            if(building[cur.l][cur.r][cur.c] == 'E')
                return cur.val;
            //상하동서남북 탐색
            for(int i=0;i<6;i++){
                int tempL = cur.l + dl[i];
                int tempR = cur.r + dr[i];
                int tempC = cur.c + dc[i];
                //방문하지 않은 빌딩 안에 움직일 수 있는 공간일 때
                if(inSpace(tempL, tempR, tempC) && !visited[tempL][tempR][tempC] && building[tempL][tempR][tempC] != '#'){
                    visited[tempL][tempR][tempC] = true;	//해당 공간 방문 확인
                    pq.add(new Info(tempL, tempR, tempC, cur.val + 1));	//해당 공간 위치 저장
                }
            }
        }
        return -1;	//출구 도착못했을 때 -1 반환

    }
    //이동하려는 공간이 빌딩에 존재하는지 확인하는 함수
    static boolean inSpace(int l, int r, int c){
        if(l >= 0 && l < L && r >= 0 && r < R && c >= 0 && c <C)
            return true;
        return false;
    }
}