[알고리즘_코딩 테스트_JAVA] 그래프-벨만-포드 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

✔ 문제 059 타임머신으로 빨리 가기

문제 바로가기 💨 

 

⬜ 핵심 아이디어

▪️ 벨만 포드

• 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
• 음수 가중치 에지가 있어도 수행할 수 있다.
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.

⬜ 핵심 구현

1. 에지 리스트로 구현한다. 최단 경로 배열은 출발 노드는 0, 나머지 노드는 무한대로 초기화 한다.
2. 모든 에지를 확인해 정답 배열을 업데이트 한다. 노드개수 - 1 만큼 아래 조건에 해당하는 최단 거리 배열을 업데이트한다. 
3. D[s]!= ∞ 이며, D[e] > D[s] + w 일 때, D[e] = [s] + w 로 배열의 값 업데이트
4. 모든 에지를 한번 씩 다시 사용해 업데이트 되는 노드가 발생하면 음수 사이클이 있다는 뜻이다.

벨만 포드 업데이트 과정

 

문제 예시 풀이 수도코드

🪄 실제 코드를 수행할 때는 에지가 저장된 순서에 따라 동작하므로 그림2처럼 거리 배열이 이론과 다르게 업데이트 된다. 하지만 이는 거리 업데이트가 빨리 일어나는 것일 뿐, 실제 최단거리구하는데 영향이 없고, 시간복잡도에도 영향이 없다.

슈도코드 작성하기

N(노드 개수), M(에지 개수)
edges(에지 정보 저장 리스트)
distance(거리 리스트) # 충분히 큰 수로 초기화

for 에지 개수만큼 반복:
    에지 리스트에 에지 정보 저장

# 벨만 포드 수행
거리 리스트에 출발 노드 0으로 초기화

for 노드개수 - 1 만큼 반복:
    for 에지 개수만큼 반복:
        현재 에지 데이터 가져오기
        if 출발 노드 무한대 X and 종료 노드값 < 출발 노드값 + 에지 가중치:
            업데이트 수행 -> 종료노드값 = 출발 노드값 + 에지 가중치

for 에지 개수만큼 반복: # 음수 사이클 존재 여부 확인
    현재 에지 데이터 가져오기
    if 출발 노드 무한대 X and 종료 노드값 < 출발 노드값 + 에지 가중치:
        업데이트 가능 -> 음수사이클 존재
        
음수 사이클 미존재 -> 거리 리스트 출력, 거리 리스트 값이 무한대일땐 -1 출력
음수 사이클 존재 -> -1 출력

PYTHON

import sys

input = sys.stdin.readline

# 입력 받기
N, M = map(int, input().split())
edges = []
dist = [sys.maxsize] * (N + 1)

# 에지 데이터 저장
for i in range(M):
    start, end, time = map(int, input().split())
    edges.append((start, end, time))

dist[1] = 0

# 벨만-포드 알고리즘으로 최단 거리 계산
for _ in range(N - 1):
    for start, end, time in edges:
        if dist[start] != sys.maxsize and dist[end] > dist[start] + time:
            dist[end] = dist[start] + time

# 음수 사이클 여부 확인
has_negative_cycle = False
for start, end, time in edges:
    if dist[start] != sys.maxsize and dist[end] > dist[start] + time:
        has_negative_cycle = True
        break

# 결과 출력
if not has_negative_cycle:
    for i in range(2, N + 1):
        if dist[i] != sys.maxsize:
            print(dist[i])
        else:
            print(-1)
else:
    print(-1)

JAVA

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static long[] dist;
    static Edge[] edges;

    public static void main(String[] args) throws java.lang.Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        edges = new Edge[M];
        dist = new long[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE); // 최단 거리 배열 초기화
        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 time = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(start, end, time);
        }
        // 벨만 포드 알고리즘
        dist[1] = 0;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Edge edge = edges[j];
                // 더 작은 최단 거리 있으면 업데이트
                if (dist[edge.start] != Integer.MAX_VALUE &&
                        dist[edge.end] > dist[edge.start] + edge.time) {
                    dist[edge.end] = dist[edge.start] + edge.time;
                }
            }
        }
        boolean mCycle = false;
        for (int i = 0; i < M; i++) { // 음수 사이클 확인
            Edge edge = edges[i];
            if (dist[edge.start] != Integer.MAX_VALUE &&
                    dist[edge.end] > dist[edge.start] + edge.time) {
                mCycle = true;
                break;
            }
        }

        if (!mCycle) { // 음의 사이클이 없을 때
            for (int i = 2; i <= N; i++) {
                if (dist[i] == Integer.MAX_VALUE) bw.write("-1\n");
                else bw.write(dist[i] + "\n");
            }
        } else { // 음 사이클이 있을때
            bw.write("-1\n");
        }
        bw.flush(); // BufferedWriter의 버퍼를 비우고 출력을 수행합니다.
    }
}

class Edge {
    int start, end, time;

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

✔ 문제 060 오민식의 고민

문제 바로가기 💨 

 

⬜ 핵심 아이디어

어려워서 하루를 통으로 날린 문제이다..자바는 아직 미해결  ㅜ일단 파이썬코드만기록해둔다. 왜 통과가 안되는지모르겠다..

이문제에서 고려해야 할 출력 케이스는 세가지이다.

1. gg - 도착 불가능
2. Gee - 도착 & 돈 무한대 (양수 무한 사이클)
3. 도착했을때 금액

1번조건은 -Min일때 gg를 출력하면되고, 3번은 도착했을때 금액을 출력하면 된다.

그런데 2번은, 양수 무한 사이클이 있는지를 체크해야 하고, 도착지 도착가능 여부도 체크해야 한다.

문제는 기존 벨만포드처럼 음의 사이클이 있는지 확인하는 것이 아니라, 도착지에 도착했을 때 돈이 무한대인지 아닌지 확인해야 한다. 즉 양의 사이클의 영향이 도착지에 전파 되었는지를 확인해야 한다.

 

무한 싸이클

 

위 그림을 보자. 0번부터 2번까지 사이클이 있는지 확인해야 한다. 벨만 포드 알고리즘은 N - 1 번째 반복까지는 거리를 측정한다. 그리고 N번째 반복에서 사이클이 있는지 확인된다. 여기서 N번째 반복에서 0번에 사이클이 있다는 것이 확인될 것이다. 하지만 아직 1번, 2번에는 그 사이클이 전파되었는지 알 수 없다.그 후, N + 1번째 반복을 실행한다면 사이클이 전파가 되어 이제 1번도 사이클이 있다는 것이 판단된다. 그리고 N + 2번째 반복이 되서야 2번에 사이클이 전파 되었음이 확인 된다. 
즉 이 문제는 기존처럼 N번 반복하는 것이 아니라 마지막 정점까지 전파가 되었음을 확인하기 위해 2 * N번 반복을 실행해야 시작 정점에서 끝 정점까지 사이클의 영향이 전파 되었는지 확인이 가능하다. 

 

예외 케이스

그리고, 양수사이클이 있다고해서 무조건 Gee를 출력하는 것도 아니다. 위 예시는 양수사이클이 있지만 목적지에 도착하지못한다.

요약해보면, Gee경우를 찾기위해 최단거리를 모두 찾은 후(N-1), N번을 다시 반복해 다시 업데이트 되는 노드를 체크(∞로 체크표기)할 것이다. 그럼  ∞ 노드들은 사이클 영향을 받은 노드를 뜻한다. 

 

 

거리 업데이트 방법

거리 업데이트는 최대를 찾는 것이기 때문에, 기존 dist[end] 비용 VS dist[start] + citycost[end] - 교통비(엣지비용 w)를 비교해 후자가 더 크면 후자로 업데이트 해준다.

 

PYTHON

import sys

def bellman_ford(N, S, E, edges, city_money):
    dist = [-float("inf") for i in range(N + 1)]  # 도시 최단 거리 초기화

    dist[S] = city_money[S]

    for _ in range(N - 1):
        for start, end, weight in edges:
            if (
                dist[start] != -float("inf")
                and dist[end] < dist[start] + city_money[end] - weight
            ):
                dist[end] = dist[start] + city_money[end] - weight

    # 음수 사이클 확인
    for _ in range(N):
        for start, end, weight in edges:
            if (
                dist[start] != -float("inf")
                and dist[end] < dist[start] + city_money[end] - weight
            ):
                dist[end] = float("inf")

    if dist[E] == float("inf"):
        return "Gee"
    elif dist[E] == -float("inf"):
        return "gg"
    else:
        return dist[E]

input = sys.stdin.readline
N, S, E, M = map(int, input().split())
edges = []
for _ in range(M):
    start, end, weight = map(int, input().split())
    edges.append((start, end, weight))
city_money = list(map(int, input().split()))
result = bellman_ford(N, S, E, edges, city_money)
print(result)

JAVA (동작X코드)

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

public class Main {
    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 S = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken()); // 교통 수단의 개수 입력받기
        
        int[][] edges = new int[M][3]; // 교통 수단의 정보를 저장할 배열 생성
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            edges[i][0] = Integer.parseInt(st.nextToken());
            edges[i][1] = Integer.parseInt(st.nextToken());
            edges[i][2] = Integer.parseInt(st.nextToken());
        }
        
        long[] cityMoney = new long[N + 1]; // 도시별 최대 벌 수 있는 돈의 액수를 저장할 배열 생성
        
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            cityMoney[i] = Long.parseLong(st.nextToken());
        }

        long[] dist = new long[N + 1];
        Arrays.fill(dist, Long.MIN_VALUE); // 최단 거리 배열 초기화
        dist[S] = cityMoney[S];

        // 벨만포드 - 최단 거리 계산
        for (int i = 0; i < N - 1; i++) {
            for (int[] edge : edges) {
                int start = edge[0];
                int end = edge[1];
                int weight = edge[2];
                if (dist[start] != Long.MIN_VALUE && dist[end] < dist[start] + cityMoney[end] - weight) {
                    dist[end] = dist[start] + cityMoney[end] - weight;
                }
            }
        }

        // 양수 사이클 확인
        for (int i = 0; i < N; i++) {
            for (int[] edge : edges) {
                int start = edge[0];
                int end = edge[1];
                int weight = edge[2];
                if (dist[start] != Long.MIN_VALUE && dist[end] < dist[start] + cityMoney[end] - weight) {
                    dist[end] = Long.MAX_VALUE;
                }
            }
        }

        if (dist[E] == Long.MIN_VALUE) System.out.println("gg"); // 도착 불가능
        else if (dist[E] == Long.MAX_VALUE) System.out.println("Gee"); // 양수사이클 연결
        else System.out.println(dist[E]); //그 이외의 경우

        br.close();
    }
}