[C++] 백준 온라인 저지 2178번 미로 탐색 풀이

아주 전형적인... BFS로 최단 거리를 찾는 문제

 

---

문제의 조건

 

1. N x M 크기의 미로가 주어진다. 

 

2. 미로의 [1, 1]에서부터 [N, M]까지 가는 최단 거리를 구해서 출력하기

=> 미로 배열의 [0, 0]에서부터 [N-1, M-1]까지의 최단 거리를 구하면 된다. 

 

---

풀이 과정

 

많이 보던 스타일이라 낯설진 않았고 BFS 알고리즘도 어느정도 익숙해서 금방 풀 수 있을 것이라 생각했지만...

여전히 백준 문제의 입력을 받는 것에 익숙하지 않았기 때문에 입력을 받는 과정에서도 착오가 있었고...

최단 거리를 구하는 식을 잘못 썼고... 등등의 이유로 오래 걸린 문제입니다.

ㅠ.ㅠ

그래도 덕분에 이젠 확실하게 알겠습니다...

근데 문제에 입력되는 숫자가 붙어서 주어진다 이런 말 말고 string형 배열로 주어지니까 알아서 쪼개 써라 이런 말 좀 써 놓으면 안 되나?

백준 사이트는 유형별로 분류 되어 있는 건 좋은데 쿨병 걸린 것 마냥 문제 설명을 하다 만 게 너무너무 많아서 입력 받는 부분 때문에 헤멘 게 한 둘이 아닙니다. 

로직은 금방 짜도 입력 받는 거 때문에 시간 날리는 경우가 한 두번도 아니고

 

 

정리된 풀이 과정

 

1. 각 타일을 BFS로 탐색하면서 타일마다의 최단 거리를 표시한다. 

 

2. [N-1, M-1] 지점에 도착하면 함께 표시한 최단 거리를 출력한다. 

 

---

코드의 흐름은 비슷하지만 컨테이너를 조금 다르게 써서 두 가지로 풀어 보았습니다. 

 

 

//1. bool 2차원 배열로 방문 표시

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M;
vector<vector<int>> dir;
void bfs(const vector<vector<int>>& maze, pair<int, int> pos)
{
    int count = 1;
    //타일의 위치(좌표)와 그 타일까지의 최단 거리를 함께 큐에 저장한다. 
    queue<pair<pair<int, int>, int>> q;
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    q.emplace(make_pair(pos, count));
    visited[pos.first][pos.second] = true;
    
    while (!q.empty())
    {
        pair<int, int> curPos = q.front().first;
        count = q.front().second;
        q.pop();
        
        if (N - 1 == curPos.first && M - 1 == curPos.second)
        {
            cout << count;
            return;
        }
        
        for (int i = 0; dir.size() > i; i++)
        {
            pair<int, int> nextPos = make_pair(curPos.first + dir[i][0], curPos.second + dir[i][1]);
            if (0 > nextPos.first || N <= nextPos.first || 0 > nextPos.second || M <= nextPos.second)
                continue;
            if (1 == maze[nextPos.first][nextPos.second] && !visited[nextPos.first][nextPos.second])
            {
                visited[nextPos.first][nextPos.second] = true;
                q.emplace(make_pair(nextPos, count + 1));
            }
        }
    }
}

int main(int argc, const char * argv[])
{
    dir.push_back({-1,0});
    dir.push_back({0,1});
    dir.push_back({1,0});
    dir.push_back({0,-1});
    
    cin >> N >> M;
    
    vector<vector<int>> maze(N, vector<int>(M, 0));
    for (int i = 0; N > i; i++)
    {
        string tmp;
        cin >> tmp;
        for (int j = 0; M > j; j++)
            maze[i][j] = tmp[j] - '0';
    }
    
    bfs(maze, make_pair(0, 0));
    
    return 0;
}

 

 

2차원 bool 배열로 방문 표시를 했을 때엔 0ms 걸렸습니다. 

 

---

//2. set 컨테이너로 방문 표시 

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int N, M;
vector<vector<int>> dir;
void bfs(const vector<vector<int>>& maze, pair<int, int> pos)
{
    int count = 1;
    queue<pair<pair<int, int>, int>> q;
    set<pair<int, int>> visited;
    q.emplace(make_pair(pos, count));
    
    while (!q.empty())
    {
        pair<int, int> curPos = q.front().first;
        count = q.front().second;
        q.pop();
        
        if (visited.end() == visited.find(curPos))
        {
            visited.insert(curPos);
            
            if (N - 1 == curPos.first && M - 1 == curPos.second)
            {
                cout << count;
                return;
            }
            
            for (int i = 0; dir.size() > i; i++)
            {
                pair<int, int> nextPos = make_pair(curPos.first + dir[i][0], curPos.second + dir[i][1]);
                if (0 <= nextPos.first && N > nextPos.first
                    && 0 <= nextPos.second && M > nextPos.second
                    && 1 == maze[nextPos.first][nextPos.second]
                    && visited.end() == visited.find(nextPos))
                    q.emplace(make_pair(nextPos, count + 1));
            }
        }
    }
}

int main(int argc, const char * argv[])
{
    dir.push_back({-1,0});
    dir.push_back({0,1});
    dir.push_back({1,0});
    dir.push_back({0,-1});
    
    cin >> N >> M;
    
    vector<vector<int>> maze(N, vector<int>(M, 0));
    for (int i = 0; N > i; i++)
    {
        string tmp;
        cin >> tmp;
        for (int j = 0; M > j; j++)
            maze[i][j] = tmp[j] - '0';
    }
    
    bfs(maze, make_pair(0, 0));
    
    return 0;
}

 

 

set 컨테이너를 써서 방문 표시를 했을 때엔 8ms가 걸렸습니다. 

역시 set에서 find 하는 과정이 오래 걸리나 봅니다. 

알고리즘을 공부하고 있는 책에서는 set으로 방문표시를 하는 방식으로 하길래 써 봤는데 시간 차이가 꽤 많이 나네요. 

결과는 똑같지만 효율성만 따진다면 2차원 배열 쓰는 것이 더 좋아 보이네요...!

 

하지만 개인적으로는 set 컨테이너로 방문 표시 하는게 좀 더 직관적이어서

일단 set으로 가 보고 효율성 통과 못 하면 2차원 배열로 가는 것으로...