코딩 테스트 [그래프] - 세일즈맨의 고민

오민식은 세일즈맨이다. 오민식의 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호가 매겨져 있다. 오민식은 A도시에서 시작해 B도시에서 끝나는 출장으로 최대한 많은 돈을 벌고 싶다.

오민식이 이용할 수 있는 교통수단에는 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 더욱이 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고 있다. 해당 값은 도시마다 다르고, 액수는 고정돼 있다. 같은 도시를 여러 번 방문할 수 있고, 도시를 방문할 때마다 그 돈을 벌게 된다. 오민식이 버는 돈보다 쓰는 돈이 많다면 도착 도시에 도착할 때 지니고 있는 돈의 액수가 음수가 될 수도 있다. 모든 교통 수단은 입력으로 주어진 방향으로만 이용할 수 있고, 여러 번 이용할 수도 있다.

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

(시간 제한 2초)

---

입력

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

출력

1번째 줄에 도시에 도착할 때 지니고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착할 수 없을 때는 'gg'를 출력한다. 그리고 오민식이 도착 도시에 도착했을 때 돈을 무한히 많이 지니고 있을 수 있다면 'Gee'를 출력한다.

예제 입력
5 0 4 5		// 노드 수, 시작, 종료, 에지 수
0 1 10
1 2 10
2 3 10
3 1 10
2 4 10
0 10 10 110 10
 
예제 출력
Gee

---

1단계 - 문제 분석하기

벨만-포트 알고리즘의 원리를 바탕으로 요구사항에 따라 내부 로직을 바꿔야 하는 문제이다.
기존 벨만-포트는 최단 거리를 구하는 알고리즘이지만, 이 문제에서는 도착 도시에 도착할 때 돈의 액수를 최대로 하고 싶기 때문에 업데이트 방식을 반대로 변경해야 한다.
또한 돈을 무한히 버는 케이스가 있다고 하는 것을 바탕으로 음수 사이클이 아닌 양수 사이클을 찾도록 변경해야 한다.
그리고 마지막으로 예외 처리가 1개 필요하다. 다음 그래프와 같이 양수 사이클이 있어도 출발 노드에서 이 양수 사이클을 이용해 도착 도시에 가지 못할 때다.

여기서는 에지의 업데이트를 N-1번이 아닌 충분히 큰 수(도시 개수 N의 최대치)만큼 추가로 돌리면서 업데이트를 수행하도록 로직을 변경하여 해결하겠다. 이렇게 변경함으로서 에지를 충분히 탐색하면서 양수 사이클에서 도달할 수 있는 모든 노드를 양수 사이클에 연결된 노드로 업데이트할 수 있다.

2단계 - 손으로 풀어 보기

1 에지 리스트에서 에지 데이터를 저장하고, 거리 배열값을 초기화한다. 최초 시작점에 해당하는 거리 배열값을 0으로 초기화한다.

2 다음 순서에 따라 변형된 벨만-포트 알고리즘을 수행한다.

1. 모든 에지와 관련된 정보를 가져와 다음 조건에 따라 거리 배열의 값을 업데이트한다.
   1-a. 시작 도시가 방문한 적이 없는 도시일 때(시작 도시 == Min) 업데이트하지 않는다.
   1-b. 시작 도시가 양수 사이클과 연결된 도시일 때(도착 도시 == Max) 도착 도시도 양수 사이클과 연결된 도시로 업데이트한다.
   1-c. '도착 도시값 < 시작 도시값 + 도착 도시 수입 - 에지 가중치' 일 때 더 많이 벌 수 있는 새로운 경로로 도착한 것이므로 값을 업데이트한다.
2. 노드보다 충분히 많은 값(N + 100)으로 1을 반복한다.
   

3 도착 도시의 값에 따라 결과를 출력한다.

1. 도착 도시의 값이 MIN == 도착하지 못한다는 뜻이므로 'gg'를 출력한다.
2. 도착 도시의 값이 MAX == 무한히 많이 벌 수 있다는 뜻이므로 'Gee'를 출력한다.
3. 이외에는 도착 도시의 값을 출력한다.
   

도착 도시의 값이 MAX 이므로 Gee 출력

3단계 - sudo코드 작성하기

N(노드 개수), M(에지 개수)
sCity(시작 도시), eCity(종료 도시)
Edges(에지 리스트 배열), cityMoney(각 도시에서 버는 수입 배열), distance(거리 배열)

거리 배열은 충분히 큰 작은 수로 초기화하기(Long.MIN_VALUE)

for(에지 개수만큼 반복)
{
	에지 리스트에 에지 정보 저장
}

거리 배열에 출발 노드를 cityMoney[출발 노드]로 초기화하기

for(노드 개수 + 100)	// 양수 사이클이 전파되도록 충분히 큰 수로 반복
{
	for(에지 개수만큼 반복)
    {
    	now = 현재 에지 데이터 가져오기
        if(출발 노드가 방문하지 않은 노드이면)
      	{
        	continue;
        }
        else if(출발 노드가 양수 사이클에 연결되어 있다면)
        {
        	종료 노드를 양수 사이클에 연결된 값으로 업데이트
        }
        else if(종료 노드 값 < 출발 노드 값 + 도착 노드에서의 수입 - 에지 가중치)
        {
        	종료 노드 값을 '출발 노드 값 + 도착 노드에서의 수입 - 에지 가중치'로 업데이트
            if(N - 1 반복 이후 업데이트 될 때)
            {
            	이 종료 노드를 양수 사이클 연결 노드로 업데이트
            }
        }
    }
}

도착 도시가 Long.MIN_VALUE라면 "gg" 출력
도착 도시가 Long.MAX_VALUE라면 "Gee" 출력
이외의 경우 도착 도시의 값 출력

4단계 - 코드 구현하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q60 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int sCity = Integer.parseInt(st.nextToken());
        int eCity = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        long[] distance = new long[N];
        long[] cityMoney = new long[N];
        Edge[] edges = new Edge[M];

        Arrays.fill(distance,Long.MIN_VALUE);   // 최단 거리 배열 초기화

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            edges[i] = new Edge(s,e,v);
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            cityMoney[i] = Long.parseLong(st.nextToken());
        }

        distance[sCity] = cityMoney[sCity];

        for(int i = 0; i <= N + 100; i++){
            for(int j = 0; j < M; j++){
                int start = edges[j].start;
                int end = edges[j].end;
                int value = edges[j].value;

                if(start == Long.MIN_VALUE){
                    continue;
                }else if(start == Long.MAX_VALUE){
                    distance[end] = Long.MAX_VALUE;
                }else if(distance[end] < distance[start] + cityMoney[end] - value){
                    distance[end] = distance[start] + cityMoney[end] - value;

                    if(i >= N - 1){
                        distance[end] = Long.MAX_VALUE;
                    }
                }
            }
        }

        if(distance[eCity] == Long.MIN_VALUE){
            System.out.println("gg");
        }else if(distance[eCity] == Long.MAX_VALUE){
            System.out.println("Gee");
        }else{
            System.out.println(distance[eCity]);
        }
    }

    static class Edge{
        int start;
        int end;
        int value;

        public Edge(int start, int end, int value){
            this.start = start;
            this.end = end;
            this.value = value;
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편