[알고리즘 / 백준] 6593 - 상범 빌딩

www.acmicpc.net/problem/6593

6593번: 상범 빌딩

 

문제는 위와 같으며 BFS 를 통해 문제를 해결할 수 있습니다.

 

1. 먼저 정육면체 단위로 공간 정보가 주어지므로 3차원 배열을 사용하여 건물 내 칸 정보 (#, ., S, E) 를 저장합니다.

2. 건물 내 정보를 저장할 때 S, E 의 위치는 따로 저장합니다.

3. 시작 위치 S를 BFS 함수에 넘겨 출구 위치 E 까지 이동하는데 걸리는 시간을 반환하도록 합니다.

4. 해당 시간이 0이 아닌 경우 탈출이 가능한 것으로 보고 그 값을 알맞게 출력합니다.

5. 해당 시간이 0인 경우 탈출할 수 없는 것으로 보고 Trapped! 메시지를 출력합니다.

 

BFS 메소드는 다음과 같습니다.

 

1. 시작 위치 (z, x, y) 값을 받아 우선순위 큐에 [해당 위치까지 이동하는데 걸린 시간(0), z, x, y] 형태로 저장합니다. 

2. 건물 내 각 위치를 방문하였는지 파악할 visited 3차원 배열을 생성하고, 처음 시작 위치를 방문한 것으로 처리합니다.

3. 이후 더이상 이동할 수 있는 공간이 없을 때까지(우선순위 큐가 빌 때까지) 아래 과정을 반복합니다.

4. 현재 위치를 우선순위 큐에서 가져옵니다. (가장 이동시간이 짧은 것을 pop)

5. 현재 위치가 출구 위치와 같은 경우 현재 위치까지 이동하는데 걸리는 시간을 반환하고 BFS 메소드를 종료합니다.

6. 그렇지 않은 경우, 상하동서남북 위치를 하나씩 확인하면서 다음 위치가 건물 범위 내이고 이동할 수 있는 칸이면서 아직 이동하지 않은 경우 우선순위 큐에 [다음 위치까지 이동하는데 걸리는 시간(현재 위치까지 이동하는데 걸린 시간 + 1), 다음 위치 z 값, 다음 위치 x 값, 다음 위치 y 값] 형태의 데이터를 저장합니다. 그리고 다음 위치를 방문한 것으로 처리합니다.

7. 출구를 찾지 못하고 더 이상 이동할 위치가 없는 경우 (우선순위 큐가 빈 경우), 0을 리턴하고 BFS 메소드를 종료합니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq

# 상하동서남북 6개의 방향으로 이동할 수 있는 위치
dz = [-1, 1, 0, 0, 0, 0]
dx = [0, 0, -1, 1, 0, 0]
dy = [0, 0, 0, 0, -1, 1]


# 시작 위치에서 도착 위치까지 이동하는데 걸리는 시간 반환
def bfs(z, x, y):
    queue = []
    heapq.heappush(queue, [0, z, x, y])  # 시작 위치 우선순위 큐에 저장 [시작 위치까지 이동하는데 걸리는 시간, 시작 위치 z, 시작 위치 x, 시작 위치 y]

    visited = [[[False for _ in range(c)] for _ in range(r)] for _ in range(l)]  # 건물 내 각 위치를 방문했는지 확인할 수 있는 3차원 배열 생성
    visited[z][x][y] = True  # 시작 위치를 방문한 것으로 처리

	# 더 이상 이동할 수 있는 칸이 없을 때까지 반복
    while queue:
        cnt, cz, cx, cy = heapq.heappop(queue)  # 현재 위치 정보 pop

		# 현재 위치와 출구 위치가 같은 경우
        if cz == ez and cx == ex and cy == ey:
            return cnt  # 현재 위치(출구 위치)까지 이동하는데 걸린 시간 반환

		# 상하동서남북 위치로 이동하면서 
        for d in range(6):
            nz = cz + dz[d]
            nx = cx + dx[d]
            ny = cy + dy[d]

            if 0 <= nz < l and 0 <= nx < r and 0 <= ny < c:  # 다음 위치가 건물 내 있고
                if building[nz][nx][ny] != '#' and not visited[nz][nx][ny]:  # 다음 위치로 이동할 수 있으면서 아직 이동하지 않은 경우
                    heapq.heappush(queue, [cnt + 1, nz, nx, ny])  # [다음 위치까지 이동하는데 걸리는 시간(현재 위치까지 이동하는데 걸린 시간 + 1), 다음 위치 z, 다음 위치 x, 다음 위치 y] 데이터 우선순위 큐에 저장
                    visited[nz][nx][ny] = True  # 다음 위치를 방문한 것으로 표시

    return 0  # 출구를 찾지 못한 채 더 이상 이동할 칸이 없는 경우 0 반환


while True:
    l, r, c = map(int, stdin.readline().split())

	# 주어진 값이 모두 0인 경우 종료
    if l == r == c == 0:
        break

    sx = 0
    sy = 0
    sz = 0

    ex = 0
    ey = 0
    ez = 0

	# 빌딩 정보를 3차원 배열에 저장
    building = [[] * r for _ in range(l)]
    for i in range(l):
        for j in range(r):
            tmp = list(map(str, stdin.readline().strip()))
            # 시작 위치가 주어진 경우
            if 'S' in tmp:
                sz = i
                sx = j
                sy = tmp.index('S')
            # 출구 위치가 주어진 경우
            elif 'E' in tmp:
                ez = i
                ex = j
                ey = tmp.index('E')
            building[i].append(tmp)
        stdin.readline()

    result = bfs(sz, sx, sy)  # 출구까지 걸리는 시간 구하기
    if result == 0:
        print("Trapped!")
    else:
        print("Escaped in", result, "minute(s).")

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	// 상하동서남북으로 이동할 수 있는 위치
    private static int[] dz = {-1, 1, 0, 0, 0, 0};
    private static int[] dx = {0, 0, -1, 1, 0, 0};
    private static int[] dy = {0, 0, 0, 0, -1, 1};

	// 층수, 행, 열 수 
    private static int l;
    private static int r;
    private static int c;

	/// 빌딩 정보
    private static String[][] building;

	// 시작 위치(z,x,y), 출구 위치(z,x,y)
    private static int sz;
    private static int sx;
    private static int sy;
    private static int ez;
    private static int ex;
    private static int ey;


    public static void main(String[] args) throws Exception {
        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());
            c = Integer.parseInt(st.nextToken());

			// 층수, 행, 열이 모두 0인 경우 종료
            if (l == 0 && r == 0 && c == 0) {
                break;
            }

			// 빌딩 정보 저장
            building = new String[l][r];
            for (int i = 0; i < l; i++) {
                for (int j = 0; j < r; j++) {
                    String tmp = br.readLine();
                    for (int k = 0; k < tmp.length(); k++) {
                        if (tmp.charAt(k) == 'S') {  // 시작 위치가 주어진 경우
                            sz = i;
                            sx = j;
                            sy = k;
                        } else if (tmp.charAt(k) == 'E') {  // 출구 위치가 주어진 경우
                            ez = i;
                            ex = j;
                            ey = k;
                        }
                    }
                    building[i][j] = tmp;
                }
                br.readLine();
            }

            int result = bfs();  // 출구까지 결리는 시간 구하기
            if (result != 0) {
                System.out.println("Escaped in " + result + " minute(s).");
            } else {
                System.out.println("Trapped!");
            }
        }

    }

    private static int bfs() {
    	// 이동할 수 있는 칸을 저장할 우선순위 큐를 생성하고
        // [해당 위치까지 이동하는데 걸리는 시간, 해당 위치 z, 해당 위치 x, 해당 위치 y] 형태 데이터를 저장하는데
        // 처음 값인 "해당 위치까지 이동하는데 걸리는 시간"을 기준으로 우선순위 정하기
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] t1, int[] t2) {
                return t1[0] - t2[0];
            }
        });
        queue.offer(new int[]{0, sz, sx, sy});  // 시작 위치를 우선순위 큐에 저장

        boolean[][][] visited = new boolean[l][r][c];  // 건물 내 각 칸을 방문했는지 확인할 3차원 배열 생성
        visited[sz][sx][sy] = true;  // 시작 위치를 방문한 것으로 처리

		// 더 이상 이동할 칸이 없을 때까지 반복
        while (!queue.isEmpty()) {
            int[] current = queue.poll();  // 현재 위치 정보 pop

			// 현재 위치가 출구 위치와 같은 경우
            if (current[1] == ez && current[2] == ex && current[3] == ey) {
                return current[0];  // 현재 위치(출구 위치)까지 이동하는데 걸린 시간 반환
            }

			// 상하동서남북으로 이동하면서
            for (int d = 0; d < 6; d++) {
                int nz = current[1] + dz[d];
                int nx = current[2] + dx[d];
                int ny = current[3] + dy[d];

                if (nz >= 0 && nz < l && nx >= 0 && nx < r && ny >= 0 && ny < c) {  // 다음 위치가 건물 내 있고
                    if (building[nz][nx].charAt(ny) != '#' && !visited[nz][nx][ny]) {  // 다음 위치로 이동할 수 있으면서 아직 이동하지 않은 경우
                        queue.offer(new int[]{current[0] + 1, nz, nx, ny});  // [다음 위치까지 이동하는데 걸리는 시간(현재 위치까지 이동하는데 걸리는 시간 + 1), 다음 위치 z, 다음 위치 x, 다음 위치 y] 데이터를 우선순위 큐에 저장
                        visited[nz][nx][ny] = true;  // 다음 위치를 방문한 것으로 처리
                    }
                }
            }
        }

        return 0;  // 출구를 찾지 못한 채 더 이상 이동할 칸이 없는 경우 0을 반환
    }
}