[BOJ] 6593. 상범 빌딩(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

빌딩에 갇힌 상법이를 살려주자..!

BFS 기본 문제이다.

여러 상자가 쌓인 토마토문제를 풀어보기 전에 풀어보면 좋을 것 같다.

상범이는 주변 or 다른 층으로 이동할 수 있다.

visit 상태 배열을 사용하지 않고 상범이가 이동했던 자리는 벽으로 수정해주면 

메모리를 절약할 수 있다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ6593 {
 
    static int L, R, C, res;
    static char building[][][];
    static int[] dr = { -1, 0, 1, 0, 0, 0}, dc = { 0, -1, 0, 1, 0, 0}, df = { 0, 0, 0, 0, 1, -1 };
    static Info start;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        while (true) {
            st = new StringTokenizer(br.readLine());
            
            L = Integer.parseInt(st.nextToken()); // 빌딩의 층 수
            R = Integer.parseInt(st.nextToken()); // row
            C = Integer.parseInt(st.nextToken()); // column
            if (L + R + C == 0) break;
 
            building = new char[L][R][C];
            for (int i = 0; i < L; i++) {
                for (int j = 0; j < R; j++) {
                    building[i][j] = br.readLine().toCharArray();
                    for (int k = 0; k < C; k++) {
                        // 시작점
                        if (building[i][j][k] == 'S') {
                            start = new Info(i, j, k);
                            building[i][j][k] = '#';
                        }
                    }
                }
                br.readLine();
            }
 
            res = process();
            if (res == -1) System.out.println("Trapped!");
            else System.out.println("Escaped in " + res + " minute(s).");
        }
    }
 
    private static int process() {
 
        int time = 0;
        Queue<Info> q = new LinkedList<>();
        q.add(start);
 
        int ff = 0, rr = 0, cc = 0, size = 0;;
        while (!q.isEmpty()) {
 
            ++time;
            size = q.size();
            while(size-- > 0) {
                Info now = q.poll();
                // 주변 or 다른 층으로 이동
                for (int d = 0; d < 6; d++) {
                    ff = now.f + df[d];
                    rr = now.r + dr[d];
                    cc = now.c + dc[d];
                    
                    // 범위를 벗어날 경우
                    if (rr < 0 || cc < 0 || rr >= R || cc >= C || ff < 0 || ff >= L) continue;
                    // 이동할 수 없다면
                    if (building[ff][rr][cc] == '#') continue;
                    
                    // 출구에 도달
                    if (building[ff][rr][cc] == 'E') return time;
                    
                    building[ff][rr][cc] = '#';
                    q.add(new Info(ff, rr, cc));
                }
            }
        }
 
        return -1;
    }
 
    static class Info {
        int f, r, c;
 
        public Info(int f, int r, int c) {
            this.f = f;
            this.r = r;
            this.c = c;
        }
        
    }
}