백준 6593번 상범 빌딩(JAVA) - BFS

백준 6593번 상범 빌딩

 

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

 

 

 

문제설명

- 빌딩의 정보가 주어진다. (   .(점)은 이동가능 / #은 이동불가능 )

- L층 R행 C열의 크기로 이루어진 빌딩

- 시작점과 도착점은 하나만 존재  - 여기서 탈출할 수 있는 최단거리를 찾는 문제.

 

 

 

접근

BFS로 접근

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static char map[][][];
    static int dist[][][];
    //    static int z, x, y;
    static int[] dx = {0, 0, -1, 0, 1, 0};
    static int[] dy = {0, 0, 0, 1, 0, -1};
    static int[] dz = {-1, 1, 0, 0, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int start_x = 0;
            int start_y = 0;
            int start_z = 0;

            int end_x = 0;
            int end_y = 0;
            int end_z = 0;

            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if(l==0 && r==0 && c==0)
                break;

            map = new char[l][r][c];
            dist = new int[l][r][c];

            for (int i = 0; i < l; i++) {
                for (int j = 0; j < r; j++) {
                    String temp = br.readLine();
                    for (int k = 0; k < c; k++) {
                        if (temp.charAt(k) == 'S') {
                            start_z = i;
                            start_x = j;
                            start_y = k;
                        }
                        if (temp.charAt(k) == 'E') {
                            end_z = i;
                            end_x = j;
                            end_y = k;
                        }
                        map[i][j][k] = temp.charAt(k);
                    }
                }
                String space = br.readLine();
            }
            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[]{start_z, start_x, start_y});

            while (!q.isEmpty()) {
                int[] temp = q.poll();
                int z = temp[0];
                int x = temp[1];
                int y = temp[2];

                for (int i = 0; i < 6; i++) {
                    int nz = z + dz[i];
                    int nx = x + dx[i];
                    int ny = y + dy[i];


                    if (nx < 0 || ny < 0 || nz < 0 || nx >= r || ny >= c || nz >= l) continue;
                    if (map[nz][nx][ny] == '#' || dist[nz][nx][ny] != 0) continue;
                    q.offer(new int[]{nz, nx, ny});
                    dist[nz][nx][ny] = dist[z][x][y] + 1;
                }

            }
            int ans = dist[end_z][end_x][end_y];

            if(ans== 0)
                System.out.println("Trapped!");
            else{
                System.out.println("Escaped in " + ans + " minute(s).");
            }

        }


    }

}

풀이

1. x,y,z축 좌표를  움직일 dx,dy,dz선언 

2. 빌딩의 정보를 받을 map, 시작점으로부터 해당 좌표까지의 거리를 담을 dist선언

3. 행과열 크기 받고 빌딩의 정보를 입력받는다.

4. 입력받으며 S(시작점), E(도착점)의 좌표를 담아둔다. (start_x,start_y,start_z / end_x,end_y,end_z)

5. 다른 최단거리 BFS와 같이 거리를 1씩 추가하면서 이동

6. while이 끝나고 도착지점이 거리가 0이아니라면(탈출가능하다면) 해당 값, 0이면 불가능 처리