[BOJ] 6593번 상범 빌딩 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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 Main {
    static final int[] dl = {0, 0, 0, 0, -1, 1};
    static final int[] dr = {-1, 1, 0, 0, 0, 0};
    static final int[] dc = {0, 0, -1, 1, 0, 0};
    static int L, R, C;
    static Pos start, end;
    static char[][][] map;
    static boolean[][][] used;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder result = new StringBuilder();
        while (true) {
            input(br);
            if (isEndOfInput()) break;
            init(br);
            getResult(result);
        }
        printResult(result);
    }

    private static void input(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        if (!st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
    }

    private static boolean isEndOfInput() {
        return L == 0 && R == 0 && C == 0;
    }

    private static void init(BufferedReader br) throws IOException {
        map = new char[L][R][C];
        used = new boolean[L][R][C];

        for (int i = 0; i < L; i++) {
            for (int j = 0; j < R; j++) {
                String input = br.readLine();
                if (input.equals("")) {
                    input = br.readLine();
                }
                for (int k = 0; k < C; k++) {
                    map[i][j][k] = input.charAt(k);
                    if (map[i][j][k] == 'S') {
                        start = new Pos(i, j, k, 0);
                    } else if (map[i][j][k] == 'E') {
                        end = new Pos(i, j, k, 0);
                    }
                }
            }
        }
    }

    private static void getResult(StringBuilder result) {
        int min = bfs();
        if (min == -1) {
            result.append("Trapped!\n");
        } else {
            result.append("Escaped in ").append(min).append(" minute(s).\n");
        }
    }

    private static int bfs() {
        Queue<Pos> q = new LinkedList<>();
        q.add(start);
        used[start.l][start.r][start.c] = true;
        while (!q.isEmpty()) {
            Pos now = q.poll();
            int l = now.l;
            int r = now.r;
            int c = now.c;
            int cnt = now.cnt;
            if (isEnd(l, r, c)) {
                return cnt;
            }

            for (int i = 0; i < 6; i++) {
                int nl = l + dl[i];
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (isOutOfRange(nl, nr, nc)) {
                    continue;
                }
                if (isNotValid(nl, nr, nc)) {
                    continue;
                }
                used[nl][nr][nc] = true;
                q.add(new Pos(nl, nr, nc, cnt + 1));
            }
        }
        return -1;
    }

    private static boolean isEnd(int l, int r, int c) {
        return l == end.l && r == end.r && c == end.c;
    }

    private static boolean isOutOfRange(int nl, int nr, int nc) {
        return nl < 0 || nr < 0 || nc < 0 || nl >= L || nr >= R || nc >= C;
    }

    private static boolean isNotValid(int nl, int nr, int nc) {
        return map[nl][nr][nc] == '#' || used[nl][nr][nc];
    }

    private static void printResult(StringBuilder result) {
        System.out.println(result);
    }

    static class Pos {

        int l;
        int r;
        int c;
        int cnt;

        public Pos(int l, int r, int c, int cnt) {
            this.l = l;
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }

}

📄 해설

접근

• 전형적인 BFS 탐색 문제
• 약간의 차이가 있다면 일반적인 BFS 문제와 달리 3차원 배열을 사용한다는 점이 있음 이점만 유의한다면 쉽게 해결 가능
• 추가로, 공백 입력 부분처리 정도만 할 수 있다면 어려운점이 없을 것
• BFS 에 대한 이론을 안다는 가정으로, 설명은 포함하지 않았음

과정

• while 루프 내에서 입력을 받는다. L, R, C 세 변수 모두 값이 0 이면 반복 종료
  • 입력 시 공백이 존재하면 다시 한줄을 입력 받는다.
  • 입력 시 시작점 S 와 탈출점 E 를 따로 저장한다.
• BFS 탐색을 수행한다.
  • 탐색 중에 탈출점을 만나면 cnt 값을 반환한다.
  • 일반적인 4방 탐색이 아니라 층 이동을 포함한 6방 탐색을 수행한다.
• 탐색 도중에 끝나지 않은 것은 탈출점에 도달하지 못하는 것이므로, -1 을 반환한다.
• 반환된 수에 따라 출력값을 조정한다. StringBuilder 를 사용해서 한번에 출력하도록 하였다.