백준 6593 상범 빌딩(bfs)

https://www.acmicpc.net/problem/6593

6593번: 상범 빌딩

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 30 + 1;
typedef struct
{
    int x, y, z;
} Dir;
typedef struct
{
    int x, y, z, cnt;
} point;
Dir dirMove[6] = {{-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, -1}, {0, 0, 1}}; //위아래(층)   상   하
string graph[MAX][MAX];
bool visited[MAX][MAX][MAX];
int L, R, C;
int startX, startY, startZ, endX, endY, endZ;
int ans;
int bfs(int x, int y, int z)
{
    visited[x][y][z] = true;
    queue<point> q;
    point start = {x, y, z, 0};
    q.push(start);
    while (!q.empty())
    {
        point now = q.front();
        q.pop();
        int curX = now.x;
        int curY = now.y;
        int curZ = now.z;
        int curCnt = now.cnt;

        if (curX == endX && curY == endY && curZ == endZ)
        {
            return curCnt;
        }
        for (int i = 0; i < 6; i++)
        {
            int nextX = curX + dirMove[i].x;
            int nextY = curY + dirMove[i].y;
            int nextZ = curZ + dirMove[i].z;

            if (0 <= nextX && nextX < L && 0 <= nextY && nextY < R && 0 <= nextZ && nextZ < C)
            {
                if (graph[nextX][nextY][nextZ] == 'E' || graph[nextX][nextY][nextZ] == '.')
                {
                    if (!visited[nextX][nextY][nextZ])
                    {
                        visited[nextX][nextY][nextZ] = true;
                        q.push({nextX, nextY, nextZ, curCnt + 1});
                    }
                }
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while (1)
    {

        cin >> L >> R >> C;
        if (!L && !R && !C)
            return 0;
        for (int i = 0; i < L; i++)
        {
            for (int j = 0; j < R; j++)
            {
                cin >> graph[i][j];
            }
        }

        for (int i = 0; i < L; i++)
        {
            for (int j = 0; j < R; j++)
            {
                for (int k = 0; k < C; k++)
                {
                    if (graph[i][j][k] == 'S')
                    {
                        startX = i;
                        startY = j;
                        startZ = k;
                    }
                    if (graph[i][j][k] == 'E')
                    {
                        endX = i;
                        endY = j;
                        endZ = k;
                    }
                }
            }
        }
        ans = bfs(startX, startY, startZ);
        if (ans == -1)
            cout << "Trapped!"
                 << "\n";
        else
            cout << "Escaped in " << ans << " minute(s)."
                 << "\n";

        for (int i = 0; i < L; i++)
        {
            for (int j = 0; j < R; j++)
            {
                for (int k = 0; k < C; k++)
                {
                    visited[i][j][k] = false;
                }
            }
        }
    }
}

오늘 알았다.... 최단 거리를 구하는 문제들은 가중치가 없을 경우 bfs, 가중치가 있을 경우 다익스트라 알고리즘으로 푸는 것이 유리하다.

 

이 문제를 dfs로 풀어보려다가 시간을 너무 많이 허비했다.....

 

여기서 가장 중요한 것은 bfs의 queue에 count값도 넣어야 한다는 사실이다!!!!!

 

count 값을 넣지않고 q.pop() 할 때마다 count를 증가시키면 최단거리가 아님에도 불구하고 count 값은 증가하게 된다. 따라서, 반드시 count 값도 queue에 넣어서 그때 그때 조건에 맞을 때만 증가될 수 있도록 코드를 구성해야한다.