문제
시작 지점에서 도착 지점에 도달할 때까지 걸린 시간을 구하여라.
빌딩은 정육면체 구조로 이루어져 있다. 대각선으로 움직일 수 없으며 현재 있는 칸에 인접한 6개의 칸(동,서,남,북,상,하)으로만 이동이 가능하다.
한 칸을 이동하는데 걸리는 시간은 1분이다.
입력
세 개의 정수 L(빌딩 층 수), R(빌딩 행 수), C(빌딩 열 수)가 주어진다. 그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 빌딩의 한 칸을 나타낸다.
문자 ‘S’는 시작 지점을 표현하며 ‘E’는 도착 지점인 출구를 표현한다.
문자 ‘.’은 지나갈 수 있는 칸이며 ‘#’은 막혀있어 지나갈 수 없는 칸이다.
입력의 끝은 L, R, C가 모두 0으로 주어질 때이다.
Ex)
// 첫번째 테스트 케이스
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
// 두번쨰 테스트 케이스
1 3 3
S##
#E#
###
// 입력의 끝
0 0 0출력
각 테스트 케이스마다 탈출하는 데에 필요한 최단 시간을 아래와 같이 출력한다.
Escaped in X minute(s).
여기서 X 는 최단시간을 의미한다.
탈출이 불가능한 경우 다음과 같이 출력한다.
Trapped!
접근
- 빌딩 구조를 담을 3차원 배열이 필요
- 좌표가 3차원 이므로
std::pair<T1, T2>를 이용하지 못해 구조체(struct)를 사용 - 두 노드 사이의 최단 경로를 찾아야 하므로 DFS가 아닌 BFS를 사용
- 하나의 칸을 이동할 때마다 시간을 증가시켜 최단 시간을 도출
구현
시작 지점을 저장할 구조체를 만든다.
struct Pos {
int l, r, c;
};l은 level이며, r은 row, c 는column을 뜻한다.
전역 변수로 입력 받을 빌딩의 층, 행, 열 수를 선언하고. 빌딩을 담을 3차원 배열과 BFS탐색에 필요한 방문 체크 배열도 함께 만들어준다.
int L, R, C;
char map[31][31][31];
bool visited[31][31][31];
int dir[6][3] = {{ 1,0,0 }, { 0,1,0 }, { 0,0,1 }, { -1,0,0 }, {0, -1, 0}, { 0,0,-1 }};
dir배열은 현재 위치에서 인접한 6개의 칸으로 이동하는 각 좌표를 담은 것이다. 예를 들어 현재 좌표가 (0, 0, 0)일 때 dir[0]을 더해주면 다음 좌표는 (1, 0 ,0)이 된다.
main()
main함수 에 전체적인 흐름을 크게 3가지로 나누었다.
- L, R, C를 입력받아 모두 0이 아닌 이상 빌딩의 구조를 입력받고 pos에 시작 위치를 저장한다.
- BFS탐색을 시작 위치부터 돌려 도착지점까지 최단 경로를 찾고, 최단 경로를 이동하는 데에 걸리는 시간이 최단 시간이므로 이를 반환한다.
- 탈출 여부를 따져 그에 걸맞는 출력을 하고 다음 테스트 케이스를 위해 사용했던 map배열과 방문체크 배열 visited를 초기화 한다.
int main(void)
{
// 테스트 케이스의 수가 정해지지 않아 while문으로 계속 반복
while (true) {
Pos pos;
cin >> L >> R >> C;
// 입력의 끝이 주어지면 종료
if (L == 0 && R == 0 && C == 0) {
break;
}
// 빌딩 구조와 시작 지점 저장
input(&pos);
// 최단 시간을 도출
int min = bfs(pos);
if (min > 0) {
cout << "Escaped in " << min << " minute(s)." << '\n';
}
else {
cout << "Trapped!" << '\n';
}
// 초기화
clear();
}
return 0;
}input()
아주 단순한 코드이며 문자 ‘S’가 입력될 시 시작 위치로 지정한다.
void input(Pos* p)
{
for (int i = 0; i < L; i++) {
for (int j = 0; j < R; j++) {
for (int k = 0; k < C; k++) {
cin >> map[i][j][k];
// 시작 위치 지정
if (map[i][j][k] == 'S') {
p->l = i, p->r = j, p->c = k;
}
}
}
}
}bfs()
문제 해결의 핵심 부분인 최단 경로를 통한 최단 시간을 도출하는 함수이다. time이 라는 변수를 만들어 하나의 칸을 이동할 때마다 +1을 해주어 전체적인 시간을 나타내게 한다. 예를 들어, 한 칸을 이동하는 데에 걸리는 시간인 1분이 지난다면 각각의 시작 위치에서 갈 수 있는 모든 칸을 queue에 넣고 시간을 늘리는 것이다. 아래 그림은 위 예제가 time = 0일 때이다.
빨간색은 각 시작점을 나타내며 초록색은 이동이 가능한 칸, 파란색은 막혀있는 칸, 노란색은 도착 지점이다.
time = 1일 때,
검정색 칸은 이미 방문한 칸을 나타낸다.
time = 2일 떄,
… 계속 반복하여 …
time = 10일 때,
그러므로 다음 time = 11일 때 도착지점에 도달한 것을 알 수 있다.
int bfs(Pos p)
{
int time = 0;
queue<Pos> q;
visited[p.l][p.r][p.c] = true; // 방문체크
q.push(p); // 시작 위치 S를 queue에 삽입
while (!q.empty()) {
int qSize = q.size();
for (int i = 0;i < qSize;i++) {
int l = q.front().l;
int r = q.front().r;
int c = q.front().c;
q.pop();
//도착 지점에 도달하면 time을 반환
if (map[l][r][c] == 'E') {
return time;
}
if (l >= 0 && l < L && r >= 0 && r < R && c >= 0 && c < C) {
// 각 시작점에 인접한 6개의 방향에 대한 탐색
for (int i = 0; i < 6; i++) {
int n_l = l + dir[i][0];
int n_r = r + dir[i][1];
int n_c = c + dir[i][2];
// 방문하지 않았고 지나갈 수 있다면 queue에 삽입
if (!visited[n_l][n_r][n_c] && map[n_l][n_r][n_c] != '#') {
visited[n_l][n_r][n_c] = true;
p.l = n_l, p.r = n_r,p.c = n_c; q.push(p);
}
}
}
}
time++;
}
return 0; // 탈출이 불가능한 경우 0을 반환
}clear()
clear함수 또한 아주 간단하며 map배열을 돌면서 모두 지나갈 수 없는 칸으로 초기화하고 방문 여부도 초기화한다.
void clear()
{
for (int i = 0; i <= L; i++) {
for (int j = 0; j <= R; j++) {
for (int k = 0; k <= C; k++) {
map[i][j][k] = '#';
visited[i][j][k] = false;
}
}
}
}