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

안유태·2023년 7월 26일
0

알고리즘

목록 보기
119/239

6593번: 상범 빌딩

bfs를 이용한 문제이다. 이번 문제는 기존 bfs와 다르게 주어지는 맵이 3차원으로 이루어져 있다. 그래서 이동 방향이 동,서,남,북,상,하 6가지가 된다. 맵을 입력받을 때 SE를 찾아 위치를 저장해주고 bfs를 돌려준다. 최초로 E 좌표에 도착했을 때가 가장 먼저 도착한 순간이므로 이 때의 countresult에 저장해 출력해주었다. 문제 자체는 어렵지 않았는데 이번에는 출력 부분에서 문제가 있었다. Escaped in 11 minute(s).형식으로 출력해야하는데 끝에 .을 빼먹은 것을 모르고 좀 해맸었다... 출력도 자세히 봐야겠다. 문제를 랜덤으로 풀다보니 요즘 bfs 문제를 많이 풀게됬다. bfs는 확실히 푸는 속도가 붙은 것 같아 기분이 좋다 ^^



#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int L, R, C;
int ls, rs, cs;
int le, re, ce;
string A[30][30];
bool check[30][30][30];
int dl[] = { 0,0,0,0,-1,1 };
int dr[] = { -1,1,0,0,0,0 };
int dc[] = { 0,0,-1,1,0,0 };
int result = -1;

void init() {
    memset(check, false, sizeof(check));

    result = -1;
}

void bfs() {
    queue <pair<pair<int, int>, pair<int, int>>> q;

    q.push({ {0,ls},{rs,cs} });
    check[ls][rs][cs] = true;

    while (!q.empty()) {
        int count = q.front().first.first;
        int l = q.front().first.second;
        int r = q.front().second.first;
        int c = q.front().second.second;

        if (l == le && r == re && c == ce) {
            result = count;
            break;
        }

        q.pop();

        for (int i = 0; i < 6; i++) {
            int nl = l + dl[i];
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nl < 0 || nr < 0 || nc < 0 || nl >= L || nr >= R || nc >= C) continue;
            if (check[nl][nr][nc]) continue;
            if (A[nl][nr][nc] == '#') continue;

            q.push({ { count + 1,nl }, { nr,nc } });
            check[nl][nr][nc] = true;
        }
    }

}

void solution() {
    bfs();

    if (result == -1) {
        cout << "Trapped!" << endl;
    }
    else {
        cout << "Escaped in " << result << " minute(s)." << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    while (1) {
        init();

        cin >> L >> R >> C;

        if (L == 0 && R == 0 && C == 0) break;

        for (int i = 0; i < L; i++) {
            for (int j = 0; j < R; j++) {
                string s;
                cin >> s;

                for (int k = 0; k < s.size(); k++) {
                    if (s[k] == 'S') {
                        ls = i;
                        rs = j;
                        cs = k;
                    }
                    else if (s[k] == 'E') {
                        le = i;
                        re = j;
                        ce = k;
                    }
                }

                A[i][j] = s;
            }
        }

        solution();
    }

    return 0;
}
profile
공부하는 개발자

0개의 댓글