[백준 2178번 C/C++] 미로 탐색

 

[백준 2178번 C/C++] 미로 탐색

 

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

2178번: 미로 탐색

---

 

 

해결전략

 

너비 우선 탐색 (BFS)

 

 

BFS (Breadth-First Search, 너비 우선 탐색) 알고리즘이 최단 거리를 찾는데 사용한다. 

그렇기 때문에 중간에 거리의 최솟값을 min으로 체크할 필요가 없다.

 

BFS 알고리즘은 시작점에서 어떤 정점까지의 최단 경로를 찾을 때 사용한다. 그 이유는 BFS가 넓이 우선으로 탐색하기 때문에, 현재 정점에서 인접한 모든 정점들을 먼저 처리한 뒤, 더 멀리 떨어진 정점들을 순차적으로 처리하기 때문이다. 따라서 BFS를 사용하면 각 노드까지의 최단 경로를 자연스럽게 계산할 수 있다.

 

BFS 알고리즘에서 각 인접한 정점들을 큐에 추가할 때, 도달하는데 걸린 거리(dist) 값을 기록한다. 이 과정이 BFS 탐색의 특성상 좁은 범위부터 차례로 진행되므로, 각 정점이 속한 범위 안에서 최초로 찾게 된 거리는 자동으로 최단 거리가 된다.

 

결론적으로, BFS 알고리즘을 사용할 경우 최단 거리를 찾는 과정에 최솟값을 확인할 필요가 없다. BFS는 그 자체로 효율적인 최단 경로 탐색 알고리즘으로, 순차적으로 노드를 탐색하면서 dist 값을 처리한다.

 

 

maze[ y ][ x ] ,  dist[ y ][ x ]

---

 

 

코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int n, m;//n 세로, m 가로
vector<vector<int>> maze;//주어진 미로
vector<vector<int>> dist;//[y][x] 배열에 도달하기까지의 거리값

int dirX[4] = { -1, 0, 1, 0 };
int dirY[4] = { 0, -1, 0, 1 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    maze.resize(n + 2, vector<int>(m + 2));
    dist.resize(n + 2, vector<int>(m + 2));

    string input;
    for(int i=1; i<=n; i++){
        cin >> input;
        for(int j=1; j<=m; j++){
            maze[i][j] = input[j - 1] - '0';
        }
    }   


    queue<pair<int, int>> Q;
    Q.push(make_pair(1, 1));//시작점 넣어주기
    dist[1][1] = 1;

    while(!Q.empty())
    {
        pair<int, int> x = Q.front();//현재 위치
        Q.pop();

        //상하좌우 이동
        for (int i=0; i<4; i++)
        {
            int newY = x.first + dirY[i];
            int newX = x.second + dirX[i];

            //이동 가능하고, 이전에 방문하지 않은 위치이면
            //문제 설정 상 maze가 1인 곳으로만 이동할 수 있다. dist[][]==0 이면 아직 안 가본 칸이라는 의미다.
	        if (maze[newY][newX] == 1 && 
                dist[newY][newX] == 0 &&
                newX > 0 && newY > 0 && newY <= n && newX <= m)
	        {
                Q.push(make_pair(newY, newX));//newY, newX 위치에서 출발하도록 Q에 넣어준다.
                dist[newY][newX] = dist[x.first][x.second] + 1;//거리 +1                
	        }
        }
    }


    cout << dist[n][m];

    return 0;
}

 

※ 주의할 점

상하좌우 탐색을 할 때 x.first = n,  dirY[ i ] = 1 인 경우 

• int newY = n + 1 이 되고

만약 아래와 같이

• maze.resize(n + 1, vector<int>(m + 1));
• dist.resize(n + 1, vector<int>(m + 1));

벡터의 크기를 잡아주면 out of range로 터지게 된다.

 

 

따라서 벡터의 크기를 아래와 같이 +1씩 더 잡아줘야 한다.

•  maze.resize(n + 2, vector<int>(m + 2));
•  dist.resize(n + 2, vector<int>(m + 2));

 

---