[구름톤 챌린지] [4주 차 학습 일기] 문제 19 - 대체 경로

문제

접근 방식

도시 하나씩 예외 도시를 설정해주어 모두 bfs를 수행했습니다

코드

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

using namespace std;

vector<vector<int>> adj;
bool visit[1001];

int start, endV;

int bfs(int except) {
    queue<pair<int, int>> q;
    q.push({start, 1});

    while (!q.empty()) {
        int check, cnt;
        tie(check, cnt) = q.front();
        q.pop();

        if(check ==endV)return cnt;

        for (int i = 0; i < adj[check].size(); ++i) {
            int V = adj[check][i];
            if (visit[V] == false && V != except) {
                q.push({V, cnt + 1});
                visit[V] = true;
            }
        }
    }

    return  -1;
}

int main() {
    int city, road;
    cin >> city >> road >> start >> endV;

    for (int i = 0; i <= city; ++i) {
        vector<int> v;
        adj.push_back(v);
    }

    for (int i = 0; i < road; ++i) {
        int c1, c2;
        cin >> c1 >> c2;
        adj[c1].push_back(c2);
        adj[c2].push_back(c1);
    }

    for (int i = 1; i <= city; ++i) {
        for (int j = 1; j <= city; ++j) {
            visit[j] = false;
        }
        if (i == start || i == endV) cout << "-1\n";
        else {
            cout << bfs(i) << "\n";
        }
    }
}

구름 IDE

https://goor.me/fBinZrb84tbzs9d8A