[C++][백준 2178] 미로탐색 - 가중치가 없는 그래프의 최단경로?

가중치가 없는 그래프의 최단경로 탐색은 BFS 로 가능하다 !

단, 경로는 유일하지 않을 수도 있다. 

 

왜 DFS는 안될까? 

 

방법 1)

스택을 이용해 푼다고 가정했을 때, 스택에 넣었을 때 visited를 true로 초기화한다고 생각해보자. 

다음 예제에서

110110

110110

111111

111101

 

위와 같은 경로로 첫 탐색이 이루어 지고, 15개의 노드를 거치게 된다.

문제는 이 경로상의 노드들은 모두 방문 한 것으로 간주되기 때문에,

실제 최단 경로상에 이 노드들이 포함되는 경우, 정답을 찾지 못하게 된다.

 

(하지만 운이 좋다면 특정 케이스의 경우 한번에 정답을 찾을수도 있다.)

 

방법 2)

가능한 모든 경로를 DFS로 구하고 최소값을 출력하면 안돼?

-> 경우의 수가 너무 많아진다. 지수 시간 복잡도 알고리즘이 되버림.

 

 

 

#include <iostream>
#include <queue>
#include <utility>
#include <stdio.h>
 
using namespace std;
 
queue<pair<int, int>> q;
queue<int> cntQueue;
 
int map[101][101];
bool visited[101][101];
int set[2] = { -1,1 };
int N, M;
 
bool borderCheck(int x, int y) {
    if (x >= 1 && x <= N && y >= 1 && y <= M) {
        return true;
    }
    else
        return false;
}
int main() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    visited[1][1] = true;
    cntQueue.push(1);
    q.push(make_pair(1, 1));
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        int cnt = cntQueue.front();
        cntQueue.pop();
 
        for (int i = 0; i < 2; i++) {
            if (borderCheck(x + set[i], y) && map[x + set[i]][y] == 1 && !visited[x + set[i]][y]) {
                if (x + set[i] == N && y == M) {
                    cout << cnt + 1 << endl;
                    return 0;
                }
                visited[x + set[i]][y] = true;
                q.push(make_pair(x + set[i], y));
                cntQueue.push(cnt + 1);
            }
        }
        for (int i = 0; i < 2; i++) {
            if (borderCheck(x, y + set[i]) && y + set[i] >= 1 && y + set[i] <= M && map[x][y + set[i]] == 1 && !visited[x][y + set[i]]) {
                if (x == N && y + set[i] == M) {
                    cout << cnt + 1 << endl;
                    return 0;
                }
                visited[x][y + set[i]] = true;
                q.push(make_pair(x, y + set[i]));
                cntQueue.push(cnt + 1);
            }
        }
    }
 
}
 
 

(문제 요약 : 1은 이동 가능, 0은 불가능, 좌측상단에서 시작해서 우측하단으로 가며 거치는 최단 거리를 구하라.)