벨만-포드 예제 - 2
문제 분석
벨만-포드 알고리즘의 원리를 바탕으로 요구사항에 따라 내부 로직을 바꿔야 하는 문제다.
기존 벨만-포드는 최단 거리를 구하는 알고리즘이지만, 이 문제에서는 도착 도시에 도착할 때 돈의 액수를 최대로 해야 하기 때문에 업데이트 방식을 반대로 변경해야 한다.
또한 돈을 무한히 많이 버는 케이스가 있다고 하는 것을 바탕으로 음수 사이클이 아닌 양수 사이클을 찾도록 변경해야 한다.
그리고 양수 사이클이 있어도 출발 노드에서 이 양수 사이클을 이용해 도착 도시에 가지 못할 때를 예외 처리가 필요하다.
이 부분을 해결하는 방법은 여러 가지가 있는데, 에지의 업데이트를
N-1번이 아닌 충분히 큰 수(N의 최댓값=50)만큼 추가로 돌리면서 업데이트를 수행하도록 한다.이유는 에지를 충분히 탐색하면서 양수 사이클에서 도달할 수 있는 모든 노드를 양수 사이클에 연결된 노드로 업데이트하기 위해서이다.
손으로 풀어보기
에지 리스트에 에지 데이터를 저장하고, 거리 리스트값을 초기화한다. 그리고 각 도시에서 벌 수 있는 돈의 최댓값을 배열(
cityMoney)에 저장한다. 최초 시작점에 해당하는 거리 리스트값은cityMoney(시작점)값으로 초기화한다.다음 순서에 따라 변형된 벨만-포드 알고리즘을 수행한다.
변형된 벨만-포드 알고리즘
모든 에지와 관련된 정보를 가져와 다음 조건에 따라 거리 리스트의 값을 업데이트한다.
시작 도시가 방문한 적이 없는 도시일 때 업데이트하지 않는다.
시작 도시가 양수 사이클과 연결된 도시일 때 도착 도시도 양수 사이클과 연결된 도시로 업데이트한다.
도착 도시 값<시작 도시 값 + 도착 도시 수입 - 에지 가중치일 때 더 많이 벌 수 있는 새로운 경로로 도착한 것이므로 값을 업데이트한다.
노드보다 충분히 많은 값으로 과정1을 반복한다.
도착 도시의 값에 따라 결과를 출력한다.
도착 도시의 값이
MIN이고, 도착하지 못할 때 'gg' 출력도착 도시의 값이
MAX이고, 무한히 많이 벌 수 있을 때 'Gee' 출력이외에는 도착 도시의 값 출력
슈도코드
n(노드 개수) start(시작 도시) end(도착 도시) m(에지 개수)
edges(에지 리스트)
distance(거리 리스트) # 처음에는 작은 수로 초기화
for m 반복:
에지 리스트 데이터 저장
cityMoney(각 도시에서 벌 수 있는 돈의 최댓값 저장)
거리 리스트에 출발 노드를 cityMoney[시작 도시]로 초기화
for n+50 반복: # 양수 사이클이 전파되도록 충분히 큰 수로 반복
for 에지 개수만큼:
현재 에지 데이터 가져오기
if 출발 노드가 미방문 노드:
continue
elif 출발 노드가 양수 사이클에 연결된 노드:
종료 노드를 양수 사이클에 연결된 노드로 업데이트
elif 종료 노드 값 < 출발 노드 값 + 도착 도시 수입 - 에지 가중치:
# 더 많은 수입을 얻는 경로가 새로 발견될 때
종료 노드 값 = 출발 노드 값 + 도착 도시 수입 - 에지 가중치 업데이트
if n-1 반복 이후 업데이트:
종료 노드를 양수 사이클 연결 노드로 업데이트
if 도착 도시가 초깃값:
gg 출력(도착 불가)
elif 도착 도시가 양수 사이클:
Gee 출력(돈을 무한히 벌 수 있음)
else:
도착 도시의 값 출력코드 구현 - 파이썬
import sys
input = sys.stdin.readline
n, startCity, endCity, m = map(int, input().split())
edges = []
distance = [-sys.maxsize] * n # 작은 수로 초기화
for _ in range(m):
s, e, c = map(int, input().split()) # 시작, 끝, 가격
edges.append((s, e, c))
cityMoney = list(map(int, input().split()))
distance[startCity] = cityMoney[startCity]
for i in range(n + 51):
for start, end, cost in edges:
if distance[start] == -sys.maxsize: # 출발 노드가 미방문 노드
continue
elif distance[start] == sys.maxsize: # 출발 노드가 양수 사이클이면 도착 노드도 양수 사이클
distance[end] = sys.maxsize
elif distance[end] < distance[start] + cityMoney[end] - cost:
distance[end] = distance[start] + cityMoney[end] - cost
if i >= n - 1: # n-1번 이후에 업데이트 된 것이라면 양수 사이클
distance[end] = sys.maxsize
print(distance)
if distance[endCity] == -sys.maxsize:
print("gg")
elif distance[endCity] == sys.maxsize:
print("Gee")
else:
print(distance[endCity])코드 구현 - 자바
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static class Edge {
int start, end, cost;
public Edge(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
}
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());
long[] distance = new long[n]; //주의! long 사용
Arrays.fill(distance, Integer.MIN_VALUE);
Edge[] edges = new Edge[m];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken()); //start
int e = Integer.parseInt(st.nextToken()); //end
int c = Integer.parseInt(st.nextToken()); //cost
edges[i] = new Edge(s, e, c);
}
int[] cityMoney = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
distance[startCity] = cityMoney[startCity];
for (int i = 0; i < n + 51; i++) {
for (Edge edge : edges) {
int start = edge.start;
int end = edge.end;
int cost = edge.cost;
if (distance[start] == Integer.MIN_VALUE) {
continue;
} else if (distance[start] == Integer.MAX_VALUE) {
distance[end] = Integer.MAX_VALUE;
} else if (distance[end] < distance[start] + cityMoney[end] - cost) {
distance[end] = distance[start] + cityMoney[end] - cost;
if (i >= n - 1) {
distance[end] = Integer.MAX_VALUE;
}
}
}
}
switch ((int) distance[endCity]) {
case Integer.MIN_VALUE -> System.out.println("gg");
case Integer.MAX_VALUE -> System.out.println("Gee");
default -> System.out.println(distance[endCity]);
}
}
}Last updated