[백준] 2178번 미로 탐색

문제: 2178번: 미로 탐색

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;


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

    int n, m;
    cin >> n >> m; 

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

    vector<vector<char>> board(n); // 맵
    vector<vector<int>> visit(n); // 방문 여부 확인
    vector<vector<int>> dist(n); // 거리
    for (int i = 0; i < n; i++) {
        board[i] = vector<char>(m);
        visit[i] = vector<int>(m);
        dist[i] = vector<int>(m);

        for (int j = 0; j < m; j++) {
            dist[i][j] = INT_MAX; // 일단 제일 큰 값 넣어놓기..
        }
    }

    for (int i = 0; i < n; i++) {
        string boardLine;
        cin >> boardLine; // 한 줄 입력 받기

        for (int j = 0; j < boardLine.size(); j++) {
            board[i][j] = boardLine[j];
        }
    }

    queue<pair<int, int>> nexts;
    nexts.push(make_pair(0, 0));
    visit[0][0] = 1; // 방문 표시
    dist[0][0] = 1;

    while (!nexts.empty()) {
        pair<int, int> cur = nexts.front();
        nexts.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (visit[nx][ny] == 1 || board[nx][ny] == '0') continue;

            nexts.push(make_pair(nx, ny));
            visit[nx][ny] = 1;
            // 다음 위치의 길이는 이전 위치에서 +1 한 값과 같다.
            // 근데 원래 길이보다 짧아야 바꿀 수 있음. 최소값 구해야 하는 거니까!
            if (dist[cur.first][cur.second] + 1 < dist[nx][ny])
                dist[nx][ny] = dist[cur.first][cur.second] + 1;
        }
    }
    cout << dist[n - 1][m - 1];

    return 0;
}

 

음.. 아래와 같은 구문이 필요할 줄 알았는데 풀고 나서 다른 풀이 확인해보니까 필요 없었다;;

// 다음 위치의 길이는 이전 위치에서 +1 한 값과 같다.
// 근데 원래 길이보다 짧아야 바꿀 수 있음. 최소값 구해야 하는 거니까!
if (dist[cur.first][cur.second] + 1 < dist[nx][ny])
    dist[nx][ny] = dist[cur.first][cur.second] + 1;

 

이유가 궁금해서 찾아봤는데 내용은 다음과 같다.

1. BFS 특성

• BFS는 탐색을 "계층적"으로 진행합니다. 즉, 먼저 시작점에서 가까운 노드들을 모두 탐색한 후 그 다음 계층(거리가 더 먼 노드)을 탐색합니다.
• 큐를 사용하여 한 계층의 노드들을 모두 처리하고 다음 계층으로 넘어가기 때문에, 특정 노드를 처음 방문할 때 이미 최단 거리로 방문하게 됩니다.

 

2. dist 갱신이 필요 없는 이유:

• BFS에서는 방문하지 않은 노드만 큐에 추가하며, 한 번 큐에 추가된 노드는 그 지점까지의 최단 경로가 이미 확정됩니다.
• 따라서 dist 값을 비교하고 갱신할 필요 없이, 큐에서 노드를 꺼내 탐색할 때 해당 노드의 거리가 확정된 최단 거리입니다.

 

3. 방문 체크와 dist 초기화:

• 이미 방문한 노드(즉, visit[nx][ny] == 1인 경우)는 다시 방문하지 않으므로, 해당 노드의 dist 값을 더 짧은 값으로 갱신할 일이 없습니다.
• 처음 방문 시 dist[nx][ny] 값이 항상 최단 거리로 기록됩니다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x09강 - BFS

[실전 알고리즘] 0x09강 - BFS