| 1 | 1753 | 최단경로 |
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오.
단, 모든 간선의 가중치는 10 이하의 자연수이다.
다익스트라 알고리즘
그래프의 한 정점(노드)에서 다른 정점까지의 최단 경로(Shortest Path)를 구하는 알고리즘
이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다.
- 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. (그리디 알고리즘)
- 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (다이나믹 프로그래밍)
- 확인되지 않은 거리는 전부 초기값을 무한(INF) 으로 잡는다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static final int MAX = Integer.MAX_VALUE;
private static int[] d;
private static boolean[] visited;
private static List<Node>[] edges;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
int V = Integer.parseInt(st.nextToken()); // 정점의 개수
int E = Integer.parseInt(st.nextToken()); // 간선의 개수
int K = Integer.parseInt(reader.readLine()); // 시작 정점
d = new int[V+1]; // K에서 다른 정점까지의 최단 경로
visited = new boolean[V+1];
edges = new List[V+1]; // edges[i]: 정점 i에서 v로 가는 가중치 w의 간선 리스트 (Node(v,w))
// 최단 경로를 MAX 값으로 초기화
for(int i = 1; i <= V; i++) {
d[i] = MAX;
edges[i] = new ArrayList<>();
}
// 간선 정보 초기화
for(int i = 0; i < E; i++) {
st = new StringTokenizer(reader.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
edges[u].add(new Node(v, w));
}
dijkstra(K);
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= V; i++) {
if(d[i] == MAX) {
sb.append("INF\n");
} else {
sb.append(d[i]).append("\n");
}
}
System.out.print(sb);
}
static void dijkstra(int start) {
// 우선순위 큐의 요소(Node)를 가중치(w)에 대해 오름차 순으로 정렬
// poll() 시 가중치가 최소인 요소를 반환
Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.getW() - o2.getW();
}
});
d[start] = 0;
queue.add(new Node(start, d[start]));
while (!queue.isEmpty()) {
Node now = queue.poll();
int u = now.getV();
visited[u] = true;
for(Node next : edges[u]) {
int v = next.getV();
if(!visited[v]) {
int w = next.getW();
if(d[u] + w < d[v]) {
d[v] = d[u] + w;
queue.add(new Node(v, d[v]));
}
}
}
}
}
static class Node {
private final int v;
private final int w;
public Node(int v, int w) {
this.v = v;
this.w = w;
}
public int getV() {
return v;
}
public int getW() {
return w;
}
}
}
- 입력 값을 List[] 에 저장 ( { [], [], [], ... } )
- edges[i]: 정점 i에서 v로 가는 가중치 w의 노드 리스트 [ Node(v,w) ]
- dijkstra(int start)
- 시작 정점에 대한 최단 경로( d[start] )를 0으로 초기화한 후 다음 탐색 정점을 저장하는 우선순위 큐에 노드로 생성하여 저장
- 우선순위 큐는 입력 노드를 시작 정점으로부터의 거리(w)에 대해 오름차 순으로 정렬하여 삭제 연산 시 시작 정점으로부터의 거리가 최소인 노드를 반환
- 현재 위치(u)에서 방문하지 않은 인접 노드(v)에 대하여 [ 시작 정점부터 v 까지의 거리 ] 를 계산하여 현재 거리 값보다 짧은 경우 값 갱신 ( d[u] + w < d[v] )
start -------> u -------> v
d[u] w
| 2 | 1504 | 특정한 최단 경로 |
방향성이 없는 그래프가 주어진다.
1번 정점에서 N번 정점으로 최단 거리로 이동하려고 할 때 다음 두 가지 조건을 만족해야 한다.
- 임의로 주어진 두 정점은 반드시 통과해야 한다.
- 한번 이동했던 정점, 한번 이동했던 간선도 다시 이동할 수 있다.
하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static final int MAX = Integer.MAX_VALUE;
private static int N;
private static int[] d1, d2;
private static List<Node>[] edges;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
N = Integer.parseInt(st.nextToken()); // 정점의 개수
int E = Integer.parseInt(st.nextToken()); // 간선의 개수
d1 = new int[N+1]; // v1에서 다른 정점까지의 최단 경로
d2 = new int[N+1]; // v2에서 다른 정점까지의 최단 경로
edges = new List[N+1]; // edges[i]: i에서 v로 가는 가중치 w의 간선 리스트 (Node(v,w))
// 최단 경로를 MAX 값으로 초기화
for(int i = 1; i <= N; i++) {
d1[i] = MAX;
d2[i] = MAX;
edges[i] = new ArrayList<>();
}
// 양방향 간선 정보
for(int i = 0; i < E; i++) {
st = new StringTokenizer(reader.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
edges[a].add(new Node(b, c));
edges[b].add(new Node(a, c));
}
// 반드시 거쳐야 하는 두 정점 (v1, v2)
st = new StringTokenizer(reader.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
dijkstra(v1, d1);
dijkstra(v2, d2);
// 1 -> v1 -> v2 -> N
int path1 = MAX;
if(d1[1] != MAX && d1[v2] != MAX && d2[N] != MAX) {
path1 = d1[1] + d1[v2] + d2[N];
}
// 1 -> v2 -> v1 -> N
int path2 = MAX;
if(d2[1] != MAX && d2[v1] != MAX && d1[N] != MAX) {
path2 = d2[1] + d2[v1] + d1[N];
}
int result = Math.min(path1, path2);
System.out.print(result == MAX ? -1 : result);
}
static void dijkstra(int start, int[] dist) {
Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.getW() - o2.getW();
}
});
boolean[] visited = new boolean[N + 1];
dist[start] = 0;
queue.add(new Node(start, dist[start]));
while (!queue.isEmpty()) {
Node now = queue.poll();
int u = now.getV();
visited[u] = true;
for(Node next : edges[u]) {
int v = next.getV();
if(!visited[v]) {
int w = next.getW();
if(dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
queue.add(new Node(v, dist[v]));
}
}
}
}
}
static class Node {
private final int v;
private final int w;
public Node(int v, int w) {
this.v = v;
this.w = w;
}
public int getV() {
return v;
}
public int getW() {
return w;
}
}
}
- 1 -> N 의 경로 중 v1, v2를 거치는 최단 경로
- path1: 1 → v1 → v2 → N
- path2: 1 → v2 → v1 → N
- path1, path2 중 최소값을 반환
- 무방향 그래프이므로 dist(1 → v1) == dist(v1 → 1), dist(1 → v2) == dist(v2 → 1)
- v1, v2를 시작 정점으로 하는 최단 경로 d1, d2를 구하고 path1, path2 를 계산
- path1: d1[1] + d1[v2] + d2[N] ( v1 → 1, v1 → v2, v2 → N )
- path2: d2[1] + d2[v1] + d1[N] ( v2 → 1, v2 → v1, v1 → N )
| 3 | 13549 | 숨바꼭질 3 |
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
- 걷는다면 1초 후에 X-1 또는 X+1로 이동
- 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static final int LENGTH = 100001;
private static int[] t;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] input = reader.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int K = Integer.parseInt(input[1]);
// 시작 정점으로부터 다른 모든 정점에 도달하는데 걸리는 최단 시간
t = new int[LENGTH];
Arrays.fill(t, Integer.MAX_VALUE);
System.out.println(dijkstra(N, K));
}
static int dijkstra(int start, int end) {
// time(시작 정점에서 v까지 도달하는데 걸리는 시간)에 대해 오름차 순 정렬
Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.getTime() - o2.getTime();
}
});
boolean[] visited = new boolean[LENGTH];
t[start] = 0;
queue.add(new Node(start, t[start]));
int min = 0;
while (!queue.isEmpty()) {
Node now = queue.poll();
int pos = now.getPos();
if(pos == end) {
min = now.getTime();
break;
}
visited[pos] = true;
// 순간 이동
// 위치: pos -> pos * 2
// 시간: time -> time + 0
int nextPos = 2 * pos;
if(nextPos < LENGTH && !visited[nextPos] && t[pos] < t[nextPos]) {
t[nextPos] = t[pos];
queue.add(new Node(nextPos, t[nextPos]));
}
// 앞으로 걷기
// 위치: pos -> pos + 1
// 시간: time -> time + 1
nextPos = pos + 1;
if(nextPos < LENGTH && !visited[nextPos] && t[pos] + 1 < t[nextPos]) {
t[nextPos] = t[pos] + 1;
queue.add(new Node(nextPos, t[nextPos]));
}
// 뒤로 걷기
// 위치: pos -> pos - 1
// 시간: time -> time + 1
nextPos = pos - 1;
if(nextPos >= 0 && !visited[nextPos] && t[pos] + 1 < t[nextPos]) {
t[nextPos] = t[pos] + 1;
queue.add(new Node(nextPos, t[nextPos]));
}
}
return min;
}
static class Node {
private final int pos;
private final int time;
public Node(int pos, int time) {
this.pos = pos;
this.time = time;
}
public int getPos() {
return pos;
}
public int getTime() {
return time;
}
}
}
다익스트라 알고리즘 이용
- 순간 이동: 가중치 +0
- 걷기: 가중치 +1
- 다음 탐색 노드를 선택할 때, 우선순위 큐(Priority Queue)는 시작 정점으로부터 도달하는 시간(Node.time)이 최소인 노드에 우선순위를 부여
| 4 | 9370 | 미확인 도착지 |
(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)
어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.
이 듀오는 대체 어디로 가고 있는 것일까?
- s에서 출발하여 목적지 후보까지 가는 경로 중 g, h 사이의 간선을 지나는 경로가 최단 경로일 때 목적지 출력
- g, h는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static final int MAX = Integer.MAX_VALUE;
private static List<Node>[] road;
private static int n;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine());
StringBuilder sb = new StringBuilder();
for(int i = 0; i < T; i++) {
StringTokenizer st = new StringTokenizer(reader.readLine());
n = Integer.parseInt(st.nextToken()); // 교차로 개수
int m = Integer.parseInt(st.nextToken()); // 도로 개수
int l = Integer.parseInt(st.nextToken()); // 목적지 후보 개수
st = new StringTokenizer(reader.readLine());
int s = Integer.parseInt(st.nextToken()); // 예술가들의 출발지
// 예술가가 지나간 길 양 옆의 교차로
int g = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
road = new List[n + 1];
for(int j = 1; j <= n; j++) {
road[j] = new ArrayList<>();
}
// 도로 정보
for(int j = 0; j < m; j++) {
st = new StringTokenizer(reader.readLine());
// a와 b 사이에 길이 d의 양방양 도로
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
road[a].add(new Node(b, d));
road[b].add(new Node(a, d));
}
int[] x = new int[l];
// 목적지 후보
for(int j = 0; j < l; j++) {
x[j] = Integer.parseInt(reader.readLine());
}
Arrays.sort(x);
for (int dest : x) {
int path = dijkstra(s, dest); // s -> dest
int path1 = dijkstra(s, g) + dijkstra(g, h) + dijkstra(h, dest); // s -> g h -> dest
int path2 = dijkstra(s, h) + dijkstra(h, g) + dijkstra(g, dest);; // s -> h g -> dest
if (Math.min(path1, path2) == path) {
sb.append(dest).append(" ");
}
}
sb.append("\n");
}
System.out.print(sb);
}
static int dijkstra(int start, int end) {
Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.getW() - o2.getW();
}
});
boolean[] visited = new boolean[n + 1];
int[] d = new int[n + 1];
Arrays.fill(d, MAX);
d[start] = 0;
queue.add(new Node(start, d[start]));
while (!queue.isEmpty()) {
Node now = queue.poll();
int pos = now.getPos();
visited[pos] = true;
for(Node next : road[pos]) {
int nextPos = next.getPos();
if(!visited[nextPos] && d[pos] + next.getW() < d[nextPos]) {
d[nextPos] = d[pos] + next.getW();
queue.add(new Node(nextPos, d[nextPos]));
}
}
}
return d[end];
}
static class Node {
private final int pos;
private final int w;
public Node(int pos, int w) {
this.pos = pos;
this.w = w;
}
public int getPos() {
return pos;
}
public int getW() {
return w;
}
}
}
- s 에서 목적지 후보 x로 가는 최단 경로 => dijkstra(s, x)
- s 에서 출발하여 g와 h사이의 간선을 지나면서 목적지 후보로 가는 최단 경로가 dijkstra(s, x) 과 같은 거리 값일 때, 목적지로 가능
- dijkstra(s, g) + dijkstra(g, h) + dijkstra(h, x)
- dijkstra(s, h) + dijkstra(h, g) + dijkstra(g, x)
- 오름차순 출력을 위해 x를 Arrays.sort() 를 이용하여 정렬
| 5 | 11657 | 타임머신 |
간선의 가중치가 음수일 수도 있을 때 벨만 포드 알고리즘을 사용하는 문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
벨만 포드 알고리즘
그래프의 한 정점(노드)에서 다른 정점까지의 최단 경로(Shortest Path)를 구하는 알고리즘
간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다.
단순히 음수 간선이 존재한다고 다익스트라 알고리즘으로 최단 경로를 구하지 못하는 것은 아니다.
하지만, 음수 간선의 순환이 포함된다면, 최단 거리가 음의 무한인 노드가 발생할 수 있다. (순환을 거칠수록 경로가 무한하게 작아짐)
밸만 포드 알고리즘은 음수 간선의 순환을 감지한다.
다익스트라 알고리즘에 비해 시간복잡도가 O(VE)로 느리다.
- 전체 간선을 하나씩 확인하여 각 간선을 거쳐 다른 노드로 가는 비용을 갱신한다. (V-1번 수행, V: 총 노의 수)
- 음수 간선 순환이 발생하는지 체크하고 싶다면 위 과정을 한 번 더 수행한다. 이 때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.
- 음수 간선 순환이 존재한다면 최단 거리를 구할 수 없다.
- 확인되지 않은 거리는 전부 초기값을 무한(INF) 으로 잡는다.
다익스트라 알고리즘 vs 벨만 포드 알고리즘
- 다익스트라 알고리즘: 매번 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
- 벨만 포드 알고리즘: 매번 모든 간선을 전부 확인 -> 다익스트라 알고리즘에서의 최적의 해를 항상 포함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static final long MAX = Long.MAX_VALUE;
private static List<Node>[] road;
private static long[] d;
private static int N;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
N = Integer.parseInt(st.nextToken()); // 도시의 개수
int M = Integer.parseInt(st.nextToken()); // 버스 노선의 개수
road = new List[N+1];
d = new long[N+1];
for(int i = 1; i <= N; i++) {
road[i] = new ArrayList<>();
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(reader.readLine());
int A = Integer.parseInt(st.nextToken()); // 시작 도시
int B = Integer.parseInt(st.nextToken()); // 도착 도시
int C = Integer.parseInt(st.nextToken()); // 이동 시간
road[A].add(new Node(B, C));
}
if(bellmanFord(1)) {
for(int i = 2; i <= N; i++) {
if(d[i] == MAX) {
System.out.println(-1);
} else {
System.out.println(d[i]);
}
}
} else {
System.out.println(-1);
}
}
static boolean bellmanFord(int start) {
Arrays.fill(d, MAX);
d[start] = 0; // 시작 노드의 최단 거리 값을 0으로 초기화
for(int i = 0; i <= N; i++) { // 아래 과정을 N번 반복 (최단 경로 찾기: N-1번, 음수 순환 찾기: 1번)
// 모든 간선 탐색
for(int j = 1; j <= N; j++) { // j: 간선의 시작 노드
for(Node node: road[j]) {
int nextPos = node.getPos(); // nextPos: 간선의 도착 노드
// 시작 노드(start)에서 j를 거쳐 nextPos로 가는 경로가 최단 거리일 경우
// start -> nextPos 의 최단 거리 값 갱신
if(d[j] != MAX && d[j] + node.getW() < d[nextPos]) {
if(i == N) { // N번째 루프에서 거리가 갱신되면 음수 순환 존재
return false;
}
d[nextPos] = d[j] + node.getW();
}
}
}
}
return true;
}
static class Node {
private final int pos;
private final int w;
public Node(int pos, int w) {
this.pos = pos;
this.w = w;
}
public int getPos() {
return pos;
}
public int getW() {
return w;
}
}
}
- 최단 경로 찾기: 모든 간선에 대한 탐색을 N-1번 반복
- 정점의 수가 N개이므로 어떤 정점도 간선을 최대 N-1개 사용하면 도달할 수 없는 정점을 제외하고 모든 정점에 도달 가능
- 첫 번째 탐색: 시작 노드로부터 간선을 최대 1개까지 거치고 다른 노드로 가는 최단 경로
- 두 번째 탐색: 시작 노드로부터 간선을 최대 2개까지 거치고 다른 노드로 가는 최단 경로
- ...
- N-1번째 탐색: 시작 노드로부터 간선을 최대 n-1개까지 거치고 다른 노드로 가는 최단 경로
- 음수 순환 찾기: N번째 단계에서 최단 경로의 갱신 여부 확인
| 6 | 11404 | 플로이드 |
n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.
모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.
플로이드 워셜 알고리즘
그래프의 모든 정점 간의 최단 경로(Shortest Path)를 구하는 알고리즘
간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다.
- 최단 경로 테이블이 2차원 배열(행렬)
- 중간 정점 k를 기준으로 모든 정점에 대해 시작 정점 i와 도착 정점 j를 탐색 (삼중 loop)
- 시간복잡도: O(n³)
- 확인되지 않은 거리는 전부 초기값을 무한(INF) 으로 설정
dist[i][j] = min( dist[i][j] , dist[i][k]+dist[k][j] )
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static final int MAX = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine()); // 도시의 개수
int m = Integer.parseInt(reader.readLine()); // 버스의 개수
int[][] cost = new int[n+1][n+1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) {
cost[i][j] = 0;
} else {
cost[i][j] = MAX;
}
}
}
for(int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(reader.readLine());
int a = Integer.parseInt(st.nextToken()); // 버스의 시작 도시
int b = Integer.parseInt(st.nextToken()); // 버스의 도착 도시
int c = Integer.parseInt(st.nextToken()); // 버스 탑승 비용
if(c < cost[a][b]) {
cost[a][b] = c;
}
}
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(cost[i][k] != MAX && cost[k][j] != MAX) {
cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
}
}
}
}
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(cost[i][j] == MAX) {
sb.append(0);
} else {
sb.append(cost[i][j]);
}
sb.append(" ");
}
sb.append("\n");
}
System.out.print(sb);
}
}
i에서 j를 이동하는 최소 비용: cost[i][j]
- 배열 초기화: 시작 도시와 도착 도시가 같다면(i = j) 비용을 0, 직행 버스가 없다면 INF(max) 값을 저장
- 노선 입력: 시작 도시와 도착 도시를 연결하는 노선(i → j)은 하나가 아닐 수 있으므로 입력과 배열 값의 비교를 통해 최소 비용을 저장
- 삼중 루프: 경유 도시(k)를 기준으로 시작 도시(i)와 도착 도시(j)의 최소 비용을 갱신
| 7 | 1956 | 운동 |
V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.
당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.
도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static final int MAX = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
int V = Integer.parseInt(st.nextToken()); // 마을의 개수
int E = Integer.parseInt(st.nextToken()); // 도로의 개수
int[][] dest = new int[V+1][V+1];
// 최단 경로 배열 초기화
for(int i = 1; i <= V; i++) {
for(int j = 1; j <= V; j++) {
if(i == j) {
dest[i][j] = 0;
} else {
dest[i][j] = MAX;
}
}
}
// 도로 정보 입력
for(int i = 0; i < E; i++) {
st = new StringTokenizer(reader.readLine());
// a번 마을에서 b번 마을로 가는 거리가 c인 도로
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
dest[a][b] = c;
}
// 플로이드 워셜 알고리즘: 모든 정점 간의 최단 경로 구하기
for(int k = 1; k <= V; k++) {
for(int i = 1; i <= V; i++) {
for(int j = 1; j <= V; j++) {
if(dest[i][k] != MAX && dest[k][j] != MAX) {
dest[i][j] = Math.min(dest[i][j], dest[i][k] + dest[k][j]);
}
}
}
}
// 최단 거리 사이클 구하기
// i -> ... -> j -> ... -> i
int min = MAX;
for(int i = 1; i <= V; i++) {
for(int j = 1; j <= V; j++) {
if(i == j) {
continue;
}
if(dest[i][j] != MAX && dest[j][i] != MAX) {
min = Math.min(min, dest[i][j] + dest[j][i]);
}
}
}
if(min == MAX) {
System.out.println(-1);
} else {
System.out.println(min);
}
}
}
- 플로이드 워셜 알고리즘을 이용하여 모든 마을 간의 최단 거리 계산 (이동할 수 없는 경우 최단 거리 값은 INF(MAX) )
- 최단 거리 사이클 구하기: 마을 i 에서 시작하여 다른 특정 마을 j를 지나 다시 i 로 돌아오는 거리가 최소인 값
'CT' 카테고리의 다른 글
| [BOJ] 30단계. 그래프와 순회 2 (0) | 2024.05.10 |
|---|---|
| [BOJ] 30단계. 그래프와 순회 1 (0) | 2024.05.07 |
| [BOJ] 29단계 스택2 (0) | 2023.07.21 |
| [BOJ] 28단계 동적 계획법 2 (0) | 2023.06.16 |
| [BOJ] 27단계 우선순위 큐 (0) | 2023.06.14 |
