[백준/Baekjoon] 1729 골목길 C++ :: Bellman-Ford

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

1738번: 골목길

---

1. Logic

1. 최적경로 즉 시작부터 목적지까지 최단거리로 가는 경우가 있는지를 먼저 파악하기 위해 BFS통해 최단거리를 확인해놓는다.

2. 벨만포드를 돌면서 최단경로를 확인하고 v번을 돌면서 마지막 사이클에서 음의 사이클을 확인한다.

3. 벨만 포드 알고리즘을 돌면서 최단경로를 갱신할 때에만 

 

주의 해야 할 사항

음의 사이클이 있다고 무조건 -1을 반환하는게 아니라 내가 가는 경로에 음의 사이클이 있으면 -1을 반환하는 것.

음의 사이클이 있어도 내가 가는 경로에 해당되지 않는다면 상관 없음

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
const int INF = 0x3f3f3f3f;

vector<pair<int, int>> adj[101]; //벨만-포드 돌기위해 정보 저장
vector<int> rev_adj[101]; //BFS로 연결되어있는지 확인하기 위해 노드 정보 저장
int dist[101]; //최단거리 저장
int trace[101]; //경로를 확인하기 위해
bool vis[101]; //BFS에서 중복 방지 방문 배열
bool check = false; //음수사이클 체크

void bellman(int start, int end) {
    memset(dist, INF, sizeof(dist));
    dist[start] = 0;

    //V-1번에 한번을 더 돌아서 음의 사이클이 있는지 확인
    for (int iter = 0; iter < n; ++iter) {
        for (int here = 1; here <= n; ++here) {
            //연결되지 않은, 계산되지 않은 최단거리는 건너뛰기
            if (dist[here] == INF) continue;
            for (auto &a : adj[here]) {
                int there = a.first;
                int cost = a.second;
                if (dist[there] > dist[here] + cost) {
                    dist[there] = dist[here] + cost;
                    trace[there] = here;
                    // V-1번까지 돈 후 마지막 음의 사이클을 돌았는지 확인
                    if (iter == n - 1 && vis[there])
                        check = true;
                }
            }
        }
    }
}

void BFS() {    
    queue<int> q;
    q.push(n);
    vis[n] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int i = 0; i < rev_adj[cur].size(); i++) {
            int next = rev_adj[cur][i];
            if (vis[next]) continue;
            vis[next] = true;
            q.push(next);
        }
    }
}

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

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back({v, -w});
        rev_adj[v].push_back(u);
    }

    BFS();

    bellman(1, n);

    if (check) {
        cout << -1;
    } else {
        vector<int> tra;
        int tr = n;
        while (tr >= 1) {
            tra.push_back(tr);
            tr = trace[tr];
        }
        
        for(int i = tra.size() - 1; i >= 0; i--) {
            cout << tra[i] << " ";
        }
    }
}

 

 

---

3. Feedback

 벨만포드는 최단거리 알고리즘이지만 이 문제에서는 cost값을 넣을 때 -를 붙혀서 넣어주어 최대 거리를 구해주었다. 활용이 필요한 문제여서 접근하는데 어려웠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐