[코딩테스트][백준] 🔥 백준 1219번 "오민식의 고민" 문제: Java으로 완벽 해결하기! 🔥

문제 링크

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

미해결

• 풀이시간 : 2시간
• 오답 이유 : 간선 자체에서 가중치가 무한으로 갈 수 있다는 것을 보고 벨만-포드 알고리즘이라는 것까지는 생각하였으나 그 이상의 접근이 어려웠다. 경로를 추적해서 해당 경로에서 사이클이 발생하는지를 따지는지까지도 접근을 했으나 경로를 구한 노드가지고 사이클 발생 여부 검사가 제대로 안된 점이 있었나 보다.
• 착각했던 점 : 순환사이클에 영향을 받는 노드를 구할 때, 시작점과 끝점이 전부 영향을 받는다고 생각하였으나 그림으로 그려보니 이해가 잘못됬음을 깨달았다. 끝점을 중심으로 영향을 받는다는 것이다. 그 이유는 끝점이 순환이 됨을 즉 값이 무한으로 갱신됨을 알아도 시작점은 영향을 받는 영향권 내 일 수도 아닐 수도 있다는 것이다.

🕒 Java 풀이시간: x

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

public class Main {
    static class Edge {
        int u, v;
        long w;

        Edge(int u, int v, long w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }

    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 startCity = Integer.parseInt(st.nextToken());
        int endCity = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            long w = Long.parseLong(st.nextToken());
            edges.add(new Edge(u, v, w));
        }

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

        String result = bellmanFord(n, startCity, endCity, edges, income);
        StringBuilder sb = new StringBuilder();
        sb.append(result);
        System.out.println(sb);
    }

    public static String bellmanFord(int n, int startCity, int endCity, List<Edge> edges, long[] income) {
        long INF = Long.MAX_VALUE;
        long[] distance = new long[n];
        Arrays.fill(distance, INF);
        distance[startCity] = -income[startCity];

        for (int i = 0; i < n - 1; i++) {
            for (Edge edge : edges) {
                int u = edge.u;
                int v = edge.v;
                long w = edge.w - income[v];
                if (distance[u] != INF && distance[u] + w < distance[v]) {
                    distance[v] = distance[u] + w;
                }
            }
        }

        boolean[] cycleInfluence = new boolean[n];
        for (Edge edge : edges) {
            int u = edge.u;
            int v = edge.v;
            long w = edge.w - income[v];
            if (distance[u] != INF && distance[u] + w < distance[v]) {
                cycleInfluence[v] = true;
            }
        }

        for (int i = 0; i < n; i++) {
            for (Edge edge : edges) {
                if (cycleInfluence[edge.u]) {
                    cycleInfluence[edge.v] = true;
                }
            }
        }

        if (cycleInfluence[endCity]) {
            return "Gee";
        } else if (distance[endCity] == INF) {
            return "gg";
        } else {
            return String.valueOf(-distance[endCity]);
        }
    }
}

이렇게 Java으로 백준의 "오민식의 고민" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊