문제 출처
백준 온라인 저지(BOJ) 2251번, POJ 2251, 정보학奥賽一本通
알고리즘 분류
너비 우선 탐색(BFS), 삼차원 그래프 탐색
문제 설명
삼차원 던전에서 가장 빠른 탈출 경로를 찾아야 한다. 던전은 여러 층으로 구성되어 있으며, 각 층은 행과 열로 구분되는 单位 격자로 이루어져 있다.
각 이동은 北, 南, 東, 西, 上, 下 중 하나의 방향으로 정확히 한 칸 이동하며, 소요 시간은 1분이다. 대각선 이동은 불가능하며, 던전의 경계는 모두 견고한 암석으로 되어 있어 외부로 나가는 것이 금지된다.
시작 위치에서 도착 위치까지 탈출 가능한지, 가능하다면 최소 몇분이 걸리는지 구해야 한다.
입력 형식
여러 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 세 정수 L, R, C가 포함된다. 이는 각각 던전의 층 수, 각 층의 행 수, 각 층의 열 수를 의미한다.
그다음에는 L개의 R×C 문자 행렬이 주어진다. 각 문자는 해당 위치의 상태를 나타낸다:
#: 암석 장애물 (통과 불가).: 빈 공간 (통과 가능)S: 시작 위치E: 탈출 위치 (목적지)
각 문자 행렬后面에는 빈 줄이 하나씩 포함된다.
입력이 0 0 0인 줄이出现하면 입력이 종료된다.
출력 형식
각 테스트 케이스마다 한 줄씩 결과를 출력한다.
- 탈출 가능한 경우:
Escaped in X minute(s).(X는 최소 탈출 시간) - 탈출 불가능한 경우:
Trapped!
제한 범위
1 ≤ L, R, C ≤ 100
입력 예시
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
출력 예시
Escaped in 11 minute(s).
Trapped!
풀이思路
이 문제는 기본적인 BFS 문제와 유사하지만, 차원이 삼차원이라는 차이가 있다. 따라서 삼차원 배열을 사용하여 문제를 해결한다.
가능한 이동 방향은 6가지이다:
- 층 증가 (+1 또는 -1)
- 행 증가/감소 (+1 또는 -1)
- 열 증가/감소 (+1 또는 -1)
BFS의 특성을 利用하면, 시작 위치에서 목표 위치까지의 최단 경로를 찾을 수 있다. BFS는 층별로 확산되어 가므로, 먼저 도달한 경로가 항상 최소 거리가 된다.
알고리즘 흐름은 다음과 같다:
- 입력으로 삼차원 맵을 읽고, 시작 위치와 목표 위치를 저장한다.
- BFS를 시작하고, 현재 위치에서 6방향으로 인접한 칸을 확인한다.
- 유효한 칸(배열 범위 내, 장애물 아님, 아직 방문하지 않음)인 경우 큐에 추가하고 거리를 기록한다.
- 목표 위치에 도달하면 현재 거리를 반환한다.
- 큐가空了 될 때까지 탐색해도 목표에 도달하지 못하면 -1을 반환한다.
구현 코드
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAX = 105;
struct Position {
int level;
int row;
int col;
};
char dungeon[MAX][MAX][MAX];
int visited[MAX][MAX][MAX];
int L, R, C;
// 6방향: 상, 하, 전, 후, 좌, 우
int dirLevel[] = {1, -1, 0, 0, 0, 0};
int dirRow[] = {0, 0, 1, -1, 0, 0};
int dirCol[] = {0, 0, 0, 0, 1, -1};
int findShortestPath(Position start, Position goal) {
memset(visited, -1, sizeof(visited));
queue<Position> q;
visited[start.level][start.row][start.col] = 0;
q.push(start);
while (!q.empty()) {
Position current = q.front();
q.pop();
// 현재 위치에서 6방향 탐색
for (int i = 0; i < 6; i++) {
int newLevel = current.level + dirLevel[i];
int newRow = current.row + dirRow[i];
int newCol = current.col + dirCol[i];
// 배열 범위 검사
if (newLevel < 0 || newLevel >= L ||
newRow < 0 || newRow >= R ||
newCol < 0 || newCol >= C) {
continue;
}
// 장애물 검사
if (dungeon[newLevel][newRow][newCol] == '#') {
continue;
}
// 이미 방문한 위치인지 검사
if (visited[newLevel][newRow][newCol] != -1) {
continue;
}
// 거리 업데이트 및 큐에 추가
visited[newLevel][newRow][newCol] =
visited[current.level][current.row][current.col] + 1;
// 목표 도달 检查
if (newLevel == goal.level &&
newRow == goal.row &&
newCol == goal.col) {
return visited[newLevel][newRow][newCol];
}
q.push({newLevel, newRow, newCol});
}
}
return -1;
}
int main() {
Position startPos, endPos;
while (cin >> L >> R >> C, L || R || C) {
// 맵 입력 및 시작/목표 위치 탐색
for (int l = 0; l < L; l++) {
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
cin >> dungeon[l][r][c];
if (dungeon[l][r][c] == 'S') {
startPos = {l, r, c};
} else if (dungeon[l][r][c] == 'E') {
endPos = {l, r, c};
}
}
}
}
int result = findShortestPath(startPos, endPos);
if (result == -1) {
cout << "Trapped!" << endl;
} else {
cout << "Escaped in " << result << " minute(s)." << endl;
}
}
return 0;
}
복잡도 분석
시간 복잡도: O(L × R × C) - 모든 칸을 최대 한 번씩 방문
공간 복잡도: O(L × R × C) - 삼차원 배열과 BFS 큐的空间
핵심 포인트
- 삼차원 BFS에서는 6방향(상, 하, 좌, 우, 앞, 뒤)으로 이동 가능
- 방문 배열을 -1로 초기화하여 미방문 상태를 표현
- BFS의 특성상 먼저 도달한 경로가 반드시 최단 경로
- 입력에서 각 층 사이에 빈 줄이 있으므로 주의 필요 (cin은 자동으로 공백을 건너뛰어 처리)