[백준] bfs- 6593번 상범빌딩 (Java)

문제링크

6593번: 상범 빌딩

 

 

접근한 방법

• 두 개의 노드 간의 거리를 구하는 문제이므로, bfs로 접근해보았다.

 

---

증명/ 풀이방법

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다.
시작지점(S가 있는 좌표)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다.
특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 배열에 넣는다.

---

소스코드 작성 방법

• 이 문제는 흔히 푸는 2차원 배열 문제에 방향 하나만 더해진 것 뿐이므로,
  모든 요소에 하나씩만 더 고려해주면 된다.

 

• 빌딩의 크기(l,r,c)를 전역 필드로 선언한다.
• 시작 지점(sl,sr,sc)과 끝 지점(el,er,ec)을 전역 필드로 선언한다.
• 빌딩의 정보(building), 방문 여부 및 거리(visited)도 전역 필드로 선언한다.
• 방향 배열 dl, dr, dc로 동,서,남,북,상,하 움직임을 저장한다.
• 층, 행, 열의 index를 저장할 수 있는 클래스를 선언한다.

 

• bfs 메소드를 선언하여 아래와 같이 처리해준다.
• 큐를 초기화 시켜준다.
• 큐에 맨 처음 좌표의 객체를 넣어준다.
• 처음 칸도 지나는 것에 포함되므로 visited[sl][sr][sc] = 0 로 처리해주어, 방문 처리 및 거리를 저장한다.
• while문으로 큐에 남아있는 게 없을 때까지 탐색을 수행한다.
  • q.poll()로 큐에서 좌표 객체를 꺼내 현재 좌표인 curL, curR, curC 필드에 저장한다.
  • 반복문으로 현재 좌표에서 6방향으로 탐색을 수행한다.
  • 이 때, 다음으로 탐색할 좌표가 탐색할 빌딩의 크기를 벗어나 진행하지 못할 경우 continue로 넘어간다.
  • 빌딩의 값이 #이 아니고 아직 방문하지 않았다면(visited의 좌표가 -1이라면) visited[nextL][nextR][nextC]에 visited[curL][curR][curC] + 1을 저장한다. (현재까지의 거리 + 1)
  • 큐에 다음 좌표의 객체를 넣어준다.

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q_6593_SangbumBuilding_20210728 {
    public static int l,r,c; // l : 층 수 | r : 행 | c : 열
    public static int sl,sr,sc;
    public static int el,er,ec;
    public static char[][][] building;
    public static int[][][] visited;
    public static int[] dl = {0, 0, 0, 0, -1, 1};
    public static int[] dr = {-1, 0, 1, 0, 0, 0};
    public static int[] dc = {0, -1, 0, 1, 0, 0};

    public static void bfs(){
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(sl, sr, sc));
        visited[sl][sr][sc] = 0;

        while (!q.isEmpty()) {
            Pair cur = q.poll();
            int curL = cur.l;
            int curR = cur.r;
            int curC = cur.c;

            for (int i = 0; i < 6; i++) {
                int nextL = curL + dl[i];
                int nextR = curR + dr[i];
                int nextC = curC + dc[i];

                if (nextL < 0 || nextL >= l || nextR < 0 || nextR >= r || nextC < 0 || nextC >= c) continue;
                if (building[nextL][nextR][nextC] != '#' && visited[nextL][nextR][nextC] == -1){
                    q.add(new Pair(nextL, nextR, nextC));
                    visited[nextL][nextR][nextC] = visited[curL][curR][curC] + 1;
                }

            }

        }

    }

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

        while(true){
            StringTokenizer 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];
            visited = 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++) {
                        building[i][j][k] = temp.charAt(k);
                        visited[i][j][k] = -1; // -1로 초기화
                        if(building[i][j][k] == 'S'){
                            sl = i;
                            sr = j;
                            sc = k;
                        }
                        if(building[i][j][k] == 'E'){
                            el = i;
                            er = j;
                            ec = k;
                        }

                    }
                }
                br.readLine();
            }

            bfs();
            if(visited[el][er][ec] == -1){
                bw.write("Trapped!\n");
            } else {
                bw.write("Escaped in "+visited[el][er][ec]+" minute(s).\n");
            }

        }

        br.close();
        bw.close();
    }

    public static class Pair{
        int l;
        int r;
        int c;

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