[백준/JAVA] 1219번: 오민식의 고민

🔺 문제

1219번: 오민식의 고민

민식이냐?

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, S, E, M;
    static Edge[] edges; // 에지 리스트
    static long[] dist;  // 거리 배열
    static long[] cityMoney; // 가격 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        N = Integer.parseInt(st.nextToken());   // 도시 수
        S = Integer.parseInt(st.nextToken());   // 시작 도시
        E = Integer.parseInt(st.nextToken());   // 도착 도시
        M = Integer.parseInt(st.nextToken());   // 교통수단 개수
        
        // 최단 거리 배열 초기화
        dist = new long[N];
        Arrays.fill(dist, Long.MIN_VALUE);
        dist[S] = 0;
        
        // 에지 리스트 채우기
        edges = new Edge[M];
        for(int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int start = Integer.parseInt(st.nextToken());
            int end   = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            
            edges[i] = new Edge(start, end, price);
        }
        
        // 가격 배열
        cityMoney = new long[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            cityMoney[i] = Long.parseLong(st.nextToken());
        }
        
        System.out.println(bellmanFord());
    }
    
    // 변형된 벨만-포드
    public static String bellmanFord() {
        dist[S] = cityMoney[S];
        
        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 price = edges[j].price;                
                
                // 출발 노드가 방문하지 않은 노드면 스킵
                if(dist[start] == Long.MIN_VALUE) continue;
                // 출발 노드가 양수 사이클에 연결된 노드라면, 종료 노드도 연결 노드로 업데이트
                else if(dist[start] == Long.MAX_VALUE)
                    dist[end] = Long.MAX_VALUE;
                // 돈 더 벌 수 있는 새 경로 발견 시, 업데이트
                else if(dist[end] < dist[start] + cityMoney[end] - price) {
                    dist[end] = dist[start] + cityMoney[end] - price;
                    
                    if(i >= N - 1) dist[end] = Long.MAX_VALUE;  // N-1 반복 이후 업데이트 되는 종료 노드, 양수 사이클 연결 노드로 변경
                }
            }
        }
        
        // 도착 도시의 값에 따른 결과 출력
        if(dist[E] == Long.MIN_VALUE)       return "gg";    // 도착 불가
        else if(dist[E] == Long.MAX_VALUE)  return "Gee";   // 양수 사이클이 연결돼 무한대 돈을 벌 수 있음
        else                                return Long.toString(dist[E]);
    }
}
 
// 에지 클래스
class Edge {
    int start, end, price;
    
    Edge(int start, int end, int price) {
        this.start = start;
        this.end = end;
        this.price = price;
    }
}

✅ 해결 아이디어
✔ 벨만-포드 알고리즘 변형!!!
- 업데이트 방식 : 돈 더 벌 수 있는 새 경로 발견 시, 업데이트
- 양수 사이클 탐색 ; N의 최대치만큼 반복

 

💥 유의사항

⇨ 시간 복잡도 :  O(MN)

 

---

🔺 다른 풀이들

- 인접 리스트 사용

[백준] 1219 : 오민식의 고민 - JAVA

 

 

- 설명이 굿

BOJ#1219 오민식의 고민

---

💬 느낀 점

응용은 또 어렵군...하핫

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ DO it 알고리즘 코딩테스트 자바편