백준1738(골목길)

jh Seo·2024년 1월 2일

백준 벨만포드 알고리즘 한번에 못 푼 문제

백준

목록 보기

169/194

개요

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

민승이는 놀러가기 위해 집을 나섰다. 민승이네 집에서 코레스코 콘도까지 가기 위해서는 복잡하게 얽혀있는 골목길들을 통과해야 한다.

그런데, 어떤 길에는 깡패가 서식하고 있어, 그 길을 지나게 되면 깡패에게 일정한 양의 금품을 갈취당하게 된다. 그런가하면, 어떤 길에는 지나가던 행인들이 흘리고 간 금품들이 떨어져 있어, 그 길을 지나게 되면 일정한 양의 금품을 획득하게 된다. 한 번 지나간 길을 다시 방문하더라도 금품을 갈취당하거나 획득한다.

골목길의 연결 상태와, 각 골목길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이 주어졌을 때, 민승이가 최대한 유리한 경로를 따라 집에서 코레스코 콘도까지 가기 위해서는 어떻게 해야 하는지 출력하는 프로그램을 작성하시오.

보유 중인 금품의 양이 음수가 될 수 있다. 최대한 유리한 경로 또는 최적의 경로는 민승이네 집에서 출발하여 코레스코 콘도에 도착하는 경로 중 금품의 양이 최대가 되는 경로이다.

접근방법

첫번째 접근 방식(틀림)

벨만 포드방식으로 접근 했다. 이 문제는 양의 사이클이 발생하므로

dist[nextNode] < dist[j]+nextDist

부호를 반대로 해야한다.

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(auto& p : adj[j]){
                int nextNode=p.first, nextDist=p.second;
                if(dist[j]!=INF&& dist[nextNode] < dist[j]+nextDist){

                    prevNode[nextNode]=j;
                    dist[nextNode] = dist[j] + nextDist;
                     //사이클이 발생
                    if (i == N - 1)
                    {
                        minusCycle = true;
                    }

이런식으로 prevNode배열을 통해 이전 노드들을 저장해뒀다.

minusCycle변수가 true가 되었다면 음의 싸이클(이 문제에서는 양의 싸이클)이 생긴 것이다.

마지막에 N-1부터 prevNode배열을 통해 0으로 갈수 있는지 탐색 했다.

minusCycle이 true가 되었다면
탐색 중간에 visited배열을 통해 싸이클이 생겼나 확인을 하는 식으로
경로에 싸이클을 체크했으나,
문제는 첫번째 값이 양의 싸이클에 휘말렸을 때이다.

이런식으로 4노드의 prev배열에는 1이 들어가고, 1-> 3 -> 2순서로 싸이클이 형성되었을 때,
-1을 출력해야 한다.

하지만 탐색때 visited 배열을 사용하게되면 prev배열을 통해 4 -> 1로 이동,
1은 처음 방문하게 되었으므로 visited가 false이므로 1->4가 출력된다.

두 번째 방법(틀림)

틀린 이유는 벨만포드 알고리즘의 원리를 어설프게 파악한 결과이다.
그냥 N번째 반복 했을 때, n개의 간선 걸쳐서 도착하는 최단경로를 갱신하는 걸로만 이해했지,
어떻게 작동하는 지 깊이 생각 안해봤다.

마지막 반복했을 때, 갱신되는 경로가 있다면 싸이클이 생기는건 알았다.
하지만 그 중 한 노드만 갱신된다고 생각 못했다.
싸이클에 해당하는 모든 노드가 다 갱신된다고 생각했다.

생각해보면 n개의 간선 걸쳐서 도착하는 최단경로가 갱신되므로
증가하기 시작하는 싸이클의 첫 노드만 증가하는게 맞다.

하지만 싸이클의 모든 노드가 다 갱신된다고 생각해서,
set을 이용해

set<int> cycleNodes

을 선언해주고,

    if (i == N - 1)

조건문 안으로 진입할때 전부 cycleNodes에 insert해줬는데 cycleNodes의 size가 1이여서 당황했었다..

세 번째 방법(맞음)

결국 다른 분들의 풀이를 보며 깨달은 방식이다..

싸이클 노드에서 도착점으로 도달여부만 판단할 수 있으면 된다.
어차피 싸이클이 시작점 및 도착점과 연결되어 있다면 무조건 싸이클을 통하게 된다.

따라서 모든 노드에서 도착점에 도달할 수 있는지를 파악해야한다.
그 방법은 경로들을 거꾸로 저장하는

vector<int> reverseV[100];

벡터를 하나 선언 해주고 경로를 뒤집어 저장한다.

    for(int i=0;i<M;i++){
        int A,B,C;
        cin>>A>>B>>C;
        adj[A-1].push_back(make_pair(B-1,C));
        reverseV[B-1].push_back(A-1);
    }

그 후, 도착지점인 N-1에서 각 노드로 BFS를 통해 방문 여부를 체크해준다.

bool BFS(int N){
    queue<int> q;
    q.push(N-1);

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int p : reverseV[cur]){
            if(!visited[p]){
                visited[p]=true;
                q.push(p);
            }
        }
    }
    return visited[0];
}

이제 남은 건 싸이클이 발생했을 때, 해당 싸이클이 도착점에 도달할 수 있는지 알 수 있는가? 이다.
단순하게 해결할 수 있다.
싸이클이 발생했을 때, 해당 노드의 visited가 true인지 체크하면 된다!

//사이클이 발생하고 사이클 노드에서 도착지점에 도달할 수 있다면
if (i == N - 1&& visited[nextNode])
{
	minusCycle = true;
}

전체 코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
const long long INF = -1e18;
vector<pair<int,int>> adj[100];
//경로를 거꾸로 저장 (도착지점에서 각 노드에 도달할 수 있는지 판별용)
vector<int> reverseV[100];
bool visited[101];

//reverseV를 통해 도착지점에서 각 노드에 도달할 수 있는지 체크한다.
bool BFS(int N){
    queue<int> q;
    q.push(N-1);

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int p : reverseV[cur]){
            if(!visited[p]){
                visited[p]=true;
                q.push(p);
            }
        }
    }
    return visited[0];
}

int main(){
    int N,M;
    cin>>N>>M;
    //얻는 금품의 가치 
    long long dist[101];
    //이전 노드
    int prevNode[101];

    fill(prevNode,prevNode+101,101);
    fill(dist,dist+101,INF);
    fill(visited,visited+101,false);

    //처음 얻는 금품은 0으로 설정
    dist[0]=0;
    bool minusCycle=false;

    for(int i=0;i<M;i++){
        int A,B,C;
        cin>>A>>B>>C;
        adj[A-1].push_back(make_pair(B-1,C));
        reverseV[B-1].push_back(A-1);
    }

    //시작지점에서 도착지점을 못가는 경우 미리 체크
    if(!BFS(N)) {
        cout<<-1;
        return 0;
    }

    //N-1번 루프보다 한번 더 돌아서 싸이클 체크
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(auto& p : adj[j]){
                int nextNode=p.first, nextDist=p.second;
                if(dist[j]!=INF&& dist[nextNode] < dist[j]+nextDist){

                    prevNode[nextNode]=j;
                    dist[nextNode] = dist[j] + nextDist;
                    //사이클이 발생하고 사이클 노드에서 도착지점에 도달할 수 있다면
                    if (i == N - 1&& visited[nextNode])
                    {
                        minusCycle = true;
                    }
                }
            }
        }
    }

    if (minusCycle)
    {
        cout<<-1;
        return 0;
    }

    //역순 설정되어 있는 prevNode를 다시 원래대로 출력하기 위함
    int cur=N-1;
    vector<int> v;
    while(cur!=0){
        v.push_back(cur);
        cur=prevNode[cur];
    }
    cout<<1<<" ";
    for(int i=v.size()-1;i>=0;i--)
    //0번부터 저장되서 1씩 더해서 출력
    cout<<v[i]+1<<" ";
}

문풀후생

정말 쉽지 않았고 시간을 많이 쓴 문제였다.
그래도 덕분에 벨만 포드 알고리즘 원리에 대해 더 깊이 이해해서 다행이다.
다음은 고마운 반례다.
https://www.acmicpc.net/board/view/110663
https://www.acmicpc.net/board/view/90841