백준 -6593 - 상범 빌딩(C++)

문제 링크입니다 https://www.acmicpc.net/problem/6593

6593번: 상범 빌딩

6방향 탐색을 이용한 탐색 문제였습니다!

문제 조건

출력 예시

 

문제 접근 방법

1. 입력과 동시에 시작 위치를 저장한다.

2. 6방향 탐색을 통해서 갈 수 있는 곳을 찾는다 -> 이전에 방문하지 않았으면서, building[i][j] == '.'인 곳

3. 탐색 중, 출구에 도착한다면 -> 이동 횟수를, 도착하지 못한다면 -> -1를 return 한다

 

 

문제 접근 방법 - 2번 + 3번

int bfs() {
    queue<qu> q;
    q.push({ start.first.second, start.second, start.first.first, 0 });
    check[start.first.first][start.first.second][start.second] = 1;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int z = q.front().z;
        int cnt = q.front().cnt;
        q.pop();
        if (building[z][x][y] == 'E') {
            return cnt;
        }
        for (int i = 0; i < 6; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            int zz = z + dz[i];
            if (xx >= 1 && xx <= R && yy >= 1 && yy <= C && zz >= 1 && zz <= L) {
                if (check[zz][xx][yy] == 0 && building[zz][xx][yy] != '#') {
                    check[zz][xx][yy] = 1;
                    q.push({ xx,yy,zz,cnt + 1 });
                }
            }
        }
    }
    return -1;
}

void solve() {
    int answer = bfs();
    if (answer == -1) cout << "Trapped!" << "\n";
    else printf("Escaped in %d minute(s).\n", answer);
}

탐색을 하는 BFS코드입니다

3차원 배열에는 높이(K), 행(R), 열(C) 순서대로 저장해야합니다.

int dx[6] = { 0,0,1,0,-1,0 };
int dy[6] = { 0,0,0,1,0,-1 };
int dz[6] = { 1,-1,0,0,0,0 };

6방향 탐색 배열입니다. Z축 위, Z축 아래, 상,하,좌,우를 탐색할 수 있습니다.

typedef struct qu {
    int x;
    int y;
    int z;
    int cnt;
}qu;

구조체에는 x, y, z축과 이동 횟수를 저장했습니다.

 

탐색의 경우의 수는 2가지입니다.

1. 출구에 도착했을 때 -> 현재 이동 횟수를 return 한다.

2. 출구에 도착하지 못했을 때 -> 6방향 탐색을 통해서 자신이 갈 수 있는 곳을 찾습니다(이전에 방문X,  building[z][x][y] == '.' 인곳) -> 찾은 후, 큐에 저장합니다. 

끝까지 출구에 도달하지 못했다면, -1을 return했습니다. answer는 return 값을 받은 변수입니다.  -> answer 값을 통해서 출력했습니다

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

int L, R, C;
char building[31][31][31];
int check[31][31][31];
int dx[6] = { 0,0,1,0,-1,0 };
int dy[6] = { 0,0,0,1,0,-1 };
int dz[6] = { 1,-1,0,0,0,0 };
pair<pair<int, int>, int> start;
typedef struct qu {
    int x;
    int y;
    int z;
    int cnt;
}qu;

int bfs() {
    queue<qu> q;
    q.push({ start.first.second, start.second, start.first.first, 0 });
    check[start.first.first][start.first.second][start.second] = 1;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int z = q.front().z;
        int cnt = q.front().cnt;
        q.pop();
        if (building[z][x][y] == 'E') {
            return cnt;
        }
        for (int i = 0; i < 6; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            int zz = z + dz[i];
            if (xx >= 1 && xx <= R && yy >= 1 && yy <= C && zz >= 1 && zz <= L) {
                if (check[zz][xx][yy] == 0 && building[zz][xx][yy] != '#') {
                    check[zz][xx][yy] = 1;
                    q.push({ xx,yy,zz,cnt + 1 });
                }
            }
        }
    }
    return -1;
}

void solve() {
    int answer = bfs();
    if (answer == -1) cout << "Trapped!" << "\n";
    else printf("Escaped in %d minute(s).\n", answer);
} 

int main()
{
    cin.tie(0);
    cout.tie(0);
    while (1) {
        cin >> L >> R >> C;
        if (L == 0 && R == 0 && C == 0) break;
        for (int k = 1; k <= L; k++) {
            for (int i = 1; i <= R; i++) {
                for (int j = 1; j <= C; j++) {
                    cin >> building[k][i][j];
                    if (building[k][i][j] == 'S') {
                        start.first.first = k;
                        start.first.second = i;
                        start.second = j;
                    }
                }
            }
        }
        solve();
        memset(check, 0, sizeof(check));
    }
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!