Do it! Java 코딩테스트 54~58번
https://github.com/KimMinheee/2023-Algorithm-Study
위상정렬
54, 백준 1516 게임개발
https://www.acmicpc.net/problem/1516
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Boj1516_게임개발하기 {
static int N;
static int[] time, result, degree;
static List<Integer>[] list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
time = new int[N + 1];
result = new int[N + 1];
degree = new int[N + 1];
list = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) list[i] = new ArrayList<>();
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
time[i] = Integer.parseInt(st.nextToken());
while (true) {
int num = Integer.parseInt(st.nextToken());
if (num == -1) break;
list[num].add(i);
degree[i]++;
}
}
topologicalSort();
}
public static void topologicalSort() {
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= N; i++) {
if (degree[i] == 0) {
queue.add(i);
result[i] = time[i];
}
}
while (!queue.isEmpty()) {
int current = queue.poll();
for (int next : list[current]) {
result[next] = Math.max(result[next], result[current] + time[next]);
degree[next]--;
if (degree[next] == 0) queue.add(next);
}
}
for (int i = 1; i <= N; i++) System.out.println(result[i]);
}
}
}게임 개발 시간을 최소화하는 문제를 위상 정렬(Topological Sort)을 이용하여 해결하고 있습니다. 위상 정렬은 방향 그래프에서 노드를 순서대로 나열하는 알고리즘입니다. 일반적으로 작업의 순서, 이벤트의 순서 등을 나열하는데 사용됩니다.
-
N은 빌딩의 수를 나타냅니다. 이것은 Integer.parseInt(br.readLine())을 통해 입력 받습니다.
-
time 배열은 각 빌딩을 짓는 데 필요한 시간을 저장하는 배열입니다. result 배열은 각 빌딩을 짓는데 걸리는 총 시간을 저장하는 배열입니다. degree 배열은 각 빌딩의 선행 조건 빌딩의 수를 저장하는 배열입니다.
-
list는 ArrayList의 배열로, 각 빌딩이 의존하는 빌딩의 목록을 저장합니다.
-
이후 for문을 통해 각 빌딩의 건설 시간과 의존성을 입력 받습니다. 각 빌딩의 의존성은 리스트에 추가되며, degree 배열에는 해당 빌딩을 건설하기 위해 선행해야 하는 빌딩의 수가 저장됩니다.
-
topologicalSort 함수를 호출하여 위상 정렬을 수행합니다. 이 함수에서는 degree가 0인 빌딩, 즉 선행 조건 없이 바로 건설할 수 있는 빌딩부터 큐에 넣습니다. 그리고 큐에서 빌딩을 하나씩 꺼내며 해당 빌딩을 건설하기 위해 선행해야 하는 빌딩의 수(degree)를 감소시키고, 그 결과 degree가 0이 된 빌딩을 큐에 추가합니다.
-
이 때 각 빌딩을 짓는데 걸리는 시간은 result 배열에 저장되는데, 이 때 각 빌딩을 짓는 데 걸리는 시간은 해당 빌딩의 건설 시간과 해당 빌딩을 짓기 위해 선행해야 하는 빌딩들을 짓는 데 걸리는 시간 중 최댓값을 선택하여 저장합니다.
-
마지막으로 각 빌딩을 짓는데 걸리는 총 시간을 출력합니다. 이 값은 result 배열에 저장되어 있습니다.
-
이 알고리즘은 위상 정렬을 이용하므로 시간 복잡도는 O(N + M)입니다. 여기서 N은 빌딩의 수, M은 의존성의 수입니다. 즉, 이 알고리즘은 빌딩의 수와 의존성의 수에 선형적으로 비례하는 시간이 걸립니다.
55, 백준 1948 임계경로 (플레)
https://www.acmicpc.net/problem/1948
다익스트라
56, 백준 1753 최단경로
https://www.acmicpc.net/problem/1753
57, 백준 1916 최소비용
https://www.acmicpc.net/problem/1916
58, 백준 1854 K번째 최단경로구하기 (플레) 나의 발표
https://www.acmicpc.net/problem/1854
import java.util.*;
import java.io.*;
public class Boj1854_K번째최단경로찾기 {
// 무한대를 나타내는 노드
private static final int INF = 1000000;
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 m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
// 각 노드에 연결된 인접 노드와 그 간선의 가중치를 저장하는 인접 리스트
ArrayList<Pair>[] adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
adj[i] = 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());
int w = Integer.parseInt(st.nextToken());
adj[u].add(new Pair(v, w));
}
//// 우선 순위 큐로(다익스트라 알고리즘에서 사용) 비용이 가장 적은 노드를 먼저 방문하도록 함.
PriorityQueue<Pair> pq = new PriorityQueue<>();
pq.offer(new Pair(1, 0));
// 각 노드까지의 K번째 최단 거리를 저장하기 위한 2차원 배열.
// dist[i][j] = i번 노드까지의 j번째 최단 거리
int[][] dist = new int[n + 1][k + 1];
for (int[] row : dist) {
Arrays.fill(row, INF);
}
dist[1][0] = 0;
// 다익스트라 알고리즘.
// 우선순위 큐에서 노드를 하나씩 꺼내며 인접한 노드들을 방문
// 방문한 노드까지의 비용이 현재 저장된 비용보다 작을 경우,
// 비용을 갱신하고 그 노드를 우선순위 큐에 추가
// 이 과정을 우선순위 큐가 비어있을 때까지 반복
while (!pq.isEmpty()) {
Pair cur = pq.poll();
if (cur.cost > dist[cur.node][k - 1]) continue;
for (Pair next : adj[cur.node]) {
int cost = cur.cost + next.cost;
if (cost < dist[next.node][k - 1]) {
dist[next.node][k - 1] = cost;
pq.offer(new Pair(next.node, cost));
Arrays.sort(dist[next.node]);
}
}
}
// 각 노드까지의 K번째 최단 거리를 출력.
// 노드까지의 K번째 최단 거리가 계산되지 않았으면 -1을 출력.
for (int i = 1; i <= n; i++) {
System.out.println(dist[i][k - 1] == INF ? -1 : dist[i][k - 1]);
}
}
// 노드와 그 노드까지의 비용을 쌍으로 저장하는 클래스.
// Comparable 인터페이스를 구현하여
// 우선순위 큐에서 비용이 적은 순서대로 정렬
static class Pair implements Comparable<Pair> {
int node, cost;
Pair(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compareTo(Pair o) {
return Integer.compare(this.cost, o.cost);
}
}
}
}
Issue
8주차는 벨만포드입니다.
