[8 - P] 질문입니다

작성한 질문수 9

0

안녕하세요 ㅎㅎ

무한대가 되는 이유, 그리고 해당 부분의 코드 설명을 해드릴게요.

문제를 잠시 보죠.

오민식이 버는 돈보다 쓰는 돈이 많다면, 도착 도시에 도착할 때 가지고 있는 돈의 액수가 음수가 될 수도 있다. 또, 같은 도시를 여러 번 방문할 수 있으며, 그 도시를 방문할 때마다 돈을 벌게 된다. 모든 교통 수단은 입력으로 주어진 방향으로만 이용할 수 있으며, 여러 번 이용할 수도 있다.

자 여기서

a -> b - > c -> b - > a

이렇게도 간선이 나올 수 있으며 이를 통해 돈을 벌 수 있습니다. 이러한 간선, 즉 사이클이 주어지면 이 사이클을 돌 때마다 +가 됩니다. 근데 문제에서

여러 번 이용할 수도 있다.

라고 했으니 돌 때마다 + 인데 무한히 돌면 무한히가 되는 것이죠. + 100만원 + 100만원.. 하다보면 무한히 가질 수 있듯이요.

음의 사이클이 일어난 시작지점이 종료노드 바로 직전이었다고

>> 음의 사이클은 판단하지 않습니다.

                if(dist[here] != -INF && dist[here] + cost[_there] - _dist > dist[_there]){
                    dist[_there] = dist[here] + cost[_there] - _dist;
                    if(i == n - 1) q.push(here);

지금 보시는 것처럼 갱신했을 때 + 가 될 때만 갱신하면서 사이클을 찾는 것을 볼 수 있습니다.

또한 문제를 보시면

오민식은 도착 도시에 도착할 때, 가지고 있는 돈의 액수를 최대로 하려고 한다. 이 최댓값을 구하는 프로그램을 작성하시오.

라고 되어있습니다. 즉, 오민식은 음의 사이클이 있다해도 해당 사이클을 여러번 방문하지 않을 것입니다.

질문주신 코드부분을 볼까요?

    while(q.size()){
        int here = q.front(); q.pop();
        for(pair<int, int> there : adj[here]){
            if(there.first == e){
                ok = 1; break;
            }
            if(!visited[there.first]){
                visited[there.first] = 1;
                q.push(there.first);
            }
        }
        if(ok) break;
    }

이부분은 사이클을 찾으면서 해당 정점까지 가느냐 안가느냐를 찾는 코드입니다.

예를 들어 d가 종료지점이라고 했을 때

a -> b - > c -> b - > a 는 양의 사이클이며

a -> b - > c -> b - > a -> d

이렇게 되면 이는 "무한"이 됩니다.

그러나

a -> b - > c -> b - > a -> e이런식으로 되면 아무리 돈을 많이 벌어도 도착지점까지 갈 수 없죠?

문제자체가

만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착했을 때 돈을 무한히 많이 가지고 있을 수 있다면 "Gee"를 출력한다.

두개를 구분해서 출력해야 하기 때문에 해당 부분을 고려를 한 것이구요.

            if(there.first == e){
                ok = 1; break;
            }

...

    else if(ok)puts("Gee");

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.