[Programmers]#Level2_게임 맵 최단 거리, 미로 찾기 유형, 최단 경로 알고리즘, BFS, 너비 우선 탐색

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. BFS, 너비 우선 탐색

 

[자료구조]#6_그래프

BFS(너비 우선 탐색)은 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. BFS는 현재 정점과 인접한 정점들을 우선적으로 탐색합니다. 일반적으로, BFS는 큐 자료구조를 활용하여 구현합니다. 

 

2. 미로 찾기 유형 문제! dx와 dy를 통해 인접 정점을 탐색!

 

1. 주어진 2차원 벡터(maps)를 그래프로 가정하고, 최단 경로 알고리즘으로 BFS를 활용합니다. 왜냐하면, 각 정점 간 거리(가중치)는 모두 동일하기 때문에, BFS를 활용하는 것이 가장 효율적입니다.
2. 이때, 다음 탐색 후보 정점을 결정할 때 현재 정점을 기준으로 위, 아래, 왼쪽, 그리고 오른쪽 정점들을 선정합니다. 주의할점은 인접 정점이 2차원 벡터의 밖으로 벗어나는 것을 방지해야 합니다.
3. 더불어, BFS 수행 과정에서 각 정점은 최단 경로 값을 업데이트 해주어야합니다.

 

---

 

#3. 코드

 

// #1. 효율성 테스트 실패

// #include <vector>
// #include <queue>
// #include <climits>
// using namespace std;

// typedef pair<int, int> p;

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

// int solution(vector<vector<int>> maps)
// {
//     int endY = maps.size() - 1;
//     int endX = maps[0].size() - 1;

//     // 우선순위 큐 선언, pair < 최단 경로 값, 정점 >
//     priority_queue<pair<int, p>, vector<pair<int, p>>, greater<pair<int, p>>> pq;
//     // 각 정점의 최단 경로 값
//     vector<vector<int>> dist(maps.size(), vector<int>(maps[0].size(), INT_MAX));
//     // 우선순위 큐에 시작 정점 삽입
//     pq.push({maps[0][0], {0, 0}});
//     // 시작 정점의 최단 경로 값 초기화
//     dist[0][0] = 1;

//     while (!pq.empty())
//     {
//         int cy = pq.top().second.first;
//         int cx = pq.top().second.second;
//         int cw = pq.top().first;
//         pq.pop();

//         if (cw > dist[cy][cx])
//             continue;

//         for (int i = 0; i < 4; ++i)
//         {
//             int ny = cy + dy[i];
//             int nx = cx + dx[i];
//             int nw = cw + maps[ny][nx];

//             if (ny < 0 || ny > endY || nx < 0 || nx > endX || maps[ny][nx] == 0 || dist[ny][nx] < nw)
//                 continue;

//             dist[ny][nx] = nw;
//             pq.push({nw, {ny, nx}});
//         }
//     }

//     if (dist[endY][endX] != INT_MAX)
//         return dist[endY][endX];
//     else
//         return -1;
// }

// #2. 정답 코드, BFS 활용
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> p;

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

int solution(vector<vector<int>> maps)
{

    int endY = maps.size() - 1;
    int endX = maps[0].size() - 1;

    // 큐 선언
    queue<p> q;
    // 각 정점의 최단 경로 값
    vector<vector<int>> dist(maps.size(), vector<int>(maps[0].size(), -1));

    // 시작 정점을 큐에 삽입 + 시작 정점의 최단 경로 값 업데이트
    q.push({0, 0});
    dist[0][0] = maps[0][0];

    while (!q.empty())
    {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (ny < 0 || ny > endY || nx < 0 || nx > endX || maps[ny][nx] == 0)
                continue;

            if (dist[ny][nx] != -1)
                continue;

            dist[ny][nx] = dist[cy][cx] + 1;
            q.push({ny, nx});
        }
    }

    if (dist[endY][endX] != INT_MAX)
        return dist[endY][endX];
    else
        return -1;
}

 

---