[백준 1219] 오민식의 고민 (JAVA)

문제

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

오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다.

오민식은 고민에 빠졌다.

어떻게 하면 최대 이윤을 낼 수 있을까?

이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다.

오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다.

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

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

1219번: 오민식의 고민

 

입력

첫째 줄에 도시의 수 N과 시작 도시, 도착 도시 그리고 교통 수단의 개수 M이 주어진다. 둘째 줄부터 M개의 줄에는 교통 수단의 정보가 주어진다. 교통 수단의 정보는 “시작 끝 가격”과 같은 형식이다. 마지막 줄에는 오민식이 각 도시에서 벌 수 있는 돈의 최댓값이 0번 도시부터 차례대로 주어진다.

N과 M은 50보다 작거나 같고, 돈의 최댓값과 교통 수단의 가격은 1,000,000보다 작거나 같은 음이 아닌 정수이다.

출력

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

예제 입력 1 

5 0 4 7
0 1 13
1 2 17
2 4 20
0 3 22
1 3 4747
2 0 10
3 4 10
0 0 0 0 0

예제 출력 1 

-32

예제 입력 2 

5 0 4 5
0 1 10
1 2 10
2 3 10
3 1 10
2 4 10
0 10 10 110 10

예제 출력 2 

Gee

예제 입력 3 

3 0 2 3
0 1 10
1 0 10
2 1 10
1000 1000 47000

예제 출력 3 

gg

예제 입력 4 

2 0 1 2
0 1 1000
1 1 10
11 11

예제 출력 4 

Gee

예제 입력 5 

1 0 0 1
0 0 10
7

예제 출력 5 

7

예제 입력 6 

5 0 4 7
0 1 13
1 2 17
2 4 20
0 3 22
1 3 4747
2 0 10
3 4 10
8 10 20 1 100000

예제 출력 6 

99988

---

어렵다.. 😒

 

벨만포드 알고리즘을 응용하는 문제이다.

 

문제 상황을 간단하게 정리해보면,

 

오민식은 교통수단을 타고 각각의 도시를 방문한다.

 

그러면 교통비용을 지불하고, 그 도시에서 벌 수 있는 돈을 벌어들인다.

 

출발 도시와 도착 도시가 주어졌을 때, 오민식이 벌 수 있는 최대 값을 구한다.

 

다만, 오민식이 도착 도시에 도달할 수 없는 경우에는 "gg" 를 출력한다.

 

만약, 오민식이 벌 수 있는 돈이 무한대라면 "Gee" 를 출력한다.

▶ 최단 거리가 아닌 최대 거리(비용)를 구하면 된다.

▶ 오민식이 벌 수 있는 돈이 무한대..? 라는 것은 양의 사이클이 발생하는 경우이다. 즉, 최대 거리를 구하면서 동시에 양의 사이클의 유무를 판별해야 한다. 

▶ 벨만 포드 알고리즘을 응용하자.

 

 

🔥 근데, 양의 사이클이 있으면 오민식은 무조건 무한대의 돈을 벌 수 있나?

▶ 아니다! 

▶ 출발 도시에서 도착 도시로 가는 경로에 양의 사이클을 형성한 노드가 없을 수도 있다. 

▶ 즉, 양의 사이클의 유무를 단순하게 판단하는 것이 아니라 양의 사이클에 의해서 도착 노드에 도달할 수 없다면 양의 사이클로 가지 않는다.

 

 

🤨 이는 어떻게 처리할 수 있을까...

▶ 벨만포드 알고리즘을 수행한 뒤에 BFS 를 한번 더 수행하여 도달 여부를 판단해도 될 것 같다.

▶ 다만 아래 방법으로 해결하는 것이 더 쉽다. (발상은 어렵다..ㅜ)

▶ 위 문제에서 도시(노드)의 개수는 최대 100 이다. 

▶ 일반적으로 벨만 포드 알고리즘으로 N-1 번 만큼 에지를 탐색하며 distance 배열을 업데이트를 할 텐데, N + 100 번정도로 충분히 많은 탐색을 해주면서 양의 사이클에서 도달할 수 있는 노드들의 모든 distance 를 MAX 로 지정해준다.

▶ 이렇게 해주면 벨만포드 알고리즘을 수행하였을 때, 도착 도시가 MAX 가 된다면 양의 사이클을 거쳐서 도착 도시에 오달할 수 있고, 이는 곧 무한대의 돈을 벌 수 있다는 것을 의미한다. Gee!

▶ 도착 도시가 MAX 가 아니라는 것은 양의 사이클에서 도착 도시로 도달할 수 없으므로 distance [도착 도시]에 저장된 값을 출력한다.

▶ 벨만 포드 알고리즘을 수행하기 전에 distnace 배열을 MIN 으로 초기화해준다. (일반적으로는 MAX 로 초기화했다. 왜 MIN 이냐면 벨만 포드 알고리즘으로 최단 거리가 아닌 최대 거리를 찾도록 변형하기 위함이다.)

▶ 벨만 포드 알고리즘을 수행하고 나서 distance [ 도착도시 ] 가 여전히 MIN 이라는 것은 오민식이 도착 도시로 도달하지 못한다는 것을 의미한다. Gee

 

 

🧐 벨만 포드 알고리즘에서 distance 를 업데이트 하는 로직은 아래와 같다.

※ 현재 탐색 중인 edge 에 대하여, (edge 클래스에는 출발 도시, 도착 도시, 교통 비용이 들어있다.) 

1. 출발 노드가 방문하지 않은 노드라면 (dist[now_edge.출발도시]==MIN) update 하지 않는다. 

2. 만약 출발 노드가 양의 사이클에 연결된 노드라면 (dist[now_edge.출발도시]==MAX) 도착 노드 또한 MAX 로 해준다.

왜냐면 A→B 의 경로에서 A 가 양의 사이클에 연결된 노드라면 당연히 B 또한 양의 사이클에 연결된 노드일 것이기 때문이다.

3. 위 경우에 모두 해당하지 않으면서, 오민식이 현재 탐색중인 edge 의 도착 노드로 갔을 때 더 많은 돈을 벌 수 있다면?

(dist[now_edge.도착도시] < dist[now_edge.출발도시] + now_edge.도착도시에서 벌 수 있는 돈 - now_edge.교통비용)

distance 를 업데이트한다.

 

 

⭐ 이 문제에서 중요한 것은 위에서 언급했듯이 양의 사이클에서 도착 도시로 도달가능하지 않는 지를 판단해야한다.

▶ 벨만-포드 알고리즘에서 사이클 여부는 엣지의 개수만큼의 업데이트 이후에, 벨만-포드 알고리즘을 더 수행했을 때 dist 값의 변화가 생기는 지 여부를 확인하면 된다.

▶ 즉, edge 의 개수만큼 업데이트를 진행 한 뒤에도 업데이트가 발생한다면 양의 사이클이 있다는 것이다.

▶ 보통인 양의 사이클 여부만 판단하면 되지만, 이 문제에서는 양의 사이클과 도착 도시가 연결되었는지 여부를 따로 판단해주어야 한다.

▶ 그러면 어떻게 할까?

▶ 엣지의 개수보다 더 많은 반복을 수행하며, 양의 사이클이 발생한다면 해당 엣지에 대하여 dist[now_edge.도착도시] = MAX 로 지정해준다.

▶ 이렇게 하면 양의 사이클에서 도달할 수 있는 모든 노드는 dist 값이 MAX 가 된다.

 

위 과정이 끝나면 dist[도착 도시] 에 따라서 Gee, gg, dist[도착 도시] 를 출력해주면 해결!

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static Edge[] graph;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(stk.nextToken()); // 노드의 수
        int start = Integer.parseInt(stk.nextToken()); // 시작도시
        int destination = Integer.parseInt(stk.nextToken()); // 도착 도시
        int m = Integer.parseInt(stk.nextToken()); // 에지의 수

        graph = new Edge[m + 1];
        long[] dist = new long[n + 1];

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            int w = Integer.parseInt(stk.nextToken());
            graph[i] = new Edge(a, b, w);
        }
        long [] money = new long[n+1];

        stk = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n; i++){
            money[i] = Integer.parseInt(stk.nextToken());
        }

        // 벨만 포드 알고리즘
        Arrays.fill(dist, Long.MIN_VALUE);
        dist[start] = money[start];

        for(int i = 0 ; i <= n+100; i++){
            for(int j = 0 ; j < m; j++){
                Edge now_edge = graph[j];
                if(dist[now_edge.st]==Long.MIN_VALUE)
                    continue;
                else if(dist[now_edge.st]==Long.MAX_VALUE){
                    dist[now_edge.end] = Long.MAX_VALUE;
                }
                else if(dist[now_edge.end] < dist[now_edge.st]+money[now_edge.end]-now_edge.cost){
                    dist[now_edge.end] = dist[now_edge.st]+money[now_edge.end]-now_edge.cost;
                    if(i>=n)
                        dist[now_edge.end] = Long.MAX_VALUE;
                }
            }
        }
        if(dist[destination] == Long.MIN_VALUE)
            bw.write("gg\n");
        else if(dist[destination] == Long.MAX_VALUE)
            bw.write("Gee\n");
        else bw.write(dist[destination]+"\n");
        bw.flush();
        bw.close();
    }

    static class Edge {
        int st;
        int end;
        int cost;

        public Edge(int s, int e, int c) {
            this.st = s;
            this.end = e;
            this.cost = c;
        }
    }
}