[백준]6593: 상범 빌딩 - JAVA

[백준]6593: 상범 빌딩

www.acmicpc.net/problem/6593

6593번: 상범 빌딩

풀이

최단거리를 찾는 문제이므로 bfs를 사용하여 탐색하였다. 시작 위치, 도착 위치를 입력 받기 위해 Node 클래스를 정의해 주었다.

 

이 문제는 좌표를 이용한 bfs문제이면서 일반적인 문제와 달리 3차원 공간에서의 bfs최단거리를 찾는 문제이다. 기존의 x, y방향으로만 이동하여 문제를 풀었던 방식을 살짝 변형하여 문제를 풀어 주었다.

 

이동 방향이 오른, 왼, 위, 아래 4방향에 위층, 아래층으로 이동하는 경우 2가지가 더해져 총 6방향으로 이동할 수 있다. 그리고 위층, 아래층으로 이동할 때에는 x, y값은 변하면 안된다. 이러한 성질을 이용하여 l, r, c의 변화량을 적절하게 미리 세팅해 풀어주었다.

 

코드

import java.util.*;
 
public class Main {    
    
    static int l, r, c;
    static char[][][] building;
    static boolean[][][] visited;
    static int[] dl = {0, 0, 0, 0, 1, -1}; //순서대로 오 왼 위 아래 위층 아래층
    static int[] dr = {0, 0, -1, 1, 0, 0};
    static int[] dc = {1, -1, 0, 0, 0, 0};
    static Node s;
    static Node e;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        while(true) {
            l = scan.nextInt();
            r = scan.nextInt();
            c = scan.nextInt();
            scan.nextLine();
            
            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 temp = scan.nextLine();
                    for(int k = 0; k < c; k++) {
                        char c = temp.charAt(k);
                        building[i][j][k] = c;
                        if(c == 'S') { //시작 지점 입력
                            s = new Node(i, j, k, 0);
                        } else if(c == 'E') { //도착 지점 입력
                            e = new Node(i, j, k, 0);
                        }
                    }
                }
                scan.nextLine();
            }
            
            visited = new boolean[l][r][c];
            int result = bfs();
            if(result == -1) System.out.println("Trapped!");
            else System.out.println("Escaped in " + result + " minute(s).");
        }
    }    
    
    public static int bfs() {
        Queue<Node> q = new LinkedList<>();
        visited[s.l][s.r][s.c] = false;
        q.offer(new Node(s.l, s.r, s.c, 0));
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            if(current.l == e.l && current.r == e.r && current.c == e.c) return current.count; 
            
            for(int i = 0; i < 6; i++) {
                int nl = current.l + dl[i];
                int nr = current.r + dr[i];
                int nc = current.c + dc[i];
                
                if(nl >= 0 && nl < l && nr >= 0 && nr < r && nc >= 0 && nc < c) {
                    if(visited[nl][nr][nc] == false && building[nl][nr][nc] != '#') {
                        visited[nl][nr][nc] = true;
                        q.offer(new Node(nl, nr, nc, current.count + 1));
                    }
                }
            }
        }
        return -1;
    }
    
    public static class Node {
        int l;
        int r;
        int c;
        int count;
        
        public Node(int l, int r, int c, int count) {
            this.l = l;
            this.r = r;
            this.c = c;
            this.count = count;
        }
    }
}