위상 정렬
위상정렬(topology sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
진입 차수는 자기 자신을 가리키는 에지의 개수입니다.
줄 세우기
Question - 2252
Code
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class N52_P2252_줄_세우기 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int node = sc.nextInt();
int edge = sc.nextInt();
ArrayList<ArrayList<Integer>> a = new ArrayList<>();
for (int i = 0; i <= node; i++) { // 여기 1부터 넣어도 되지 않을까 ? 안된다.
a.add(new ArrayList<>());
}
// 그래프, 진입 차수 동시에 처리
int[] in = new int[node + 1];
for (int i = 0; i < edge; i++) {
int S = sc.nextInt();
int E = sc.nextInt();
a.get(S).add(E);
in[E]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= node; i++) {
if (in[i] == 0) q.offer(i); // offer ??
}
while (!q.isEmpty()) {
int now = q.poll();
System.out.print(now + " ");
for (int next : a.get(now)) {
in[next]--;
if (in[next] == 0) q.offer(next);
}
}
}
}
Idea
reference
게임 개발하기
Question - 1516
Code
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class N54_P1516_게임_개발하기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int buildingNum = Integer.parseInt(br.readLine());
ArrayList<ArrayList<Integer>> a = new ArrayList<>();
for (int i = 0; i <= buildingNum; i++) {
a.add(new ArrayList<>());
}
int[] in = new int[buildingNum + 1];
int[] time = new int[buildingNum + 1];
for (int i = 1; i <= buildingNum; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
time[i] = Integer.parseInt(st.nextToken());
while (true) {
int preTemp = Integer.parseInt(st.nextToken());
if (preTemp == -1)
break;
a.get(preTemp).add(i);
in[i]++;
}
}
// 위상 정렬
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= buildingNum; i++) {
if (in[i] == 0) {
q.offer(i);
}
}
int[] result = new int[buildingNum + 1];
while (!q.isEmpty()) {
int now = q.poll();
for (int next : a.get(now)) {
in[next]--;
result[next] = Math.max(result[next], result[now] + time[now]);
if (in[next] == 0){
q.offer(next);
}
}
}
for (int i = 1; i <= buildingNum; i++) {
System.out.println(result[i] + time[i]);
}
}
}
Idea
reference
임계 경로 구하기
Question - 1948
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class N55_P1948_임계_경로_구하기 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int node = Integer.parseInt(br.readLine()); // 도시
int edge = Integer.parseInt(br.readLine()); // 도로
// 출발 도시의 번호
// 도착 도시 번호
// 도로를 지나는 데 걸리는 시간
ArrayList<ArrayList<dNode>> a = new ArrayList<>();
ArrayList<ArrayList<dNode>> reverse = new ArrayList<>();
// 그래프 초기화
for (int i = 0; i <= node; i++) {
a.add(new ArrayList<>());
reverse.add(new ArrayList<>());
}
// 진입 차수 배열 : 자기 자신을 가리키는 에지의 개수
int[] in = new int[node + 1];
for (int i = 0; i < edge; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken()); // 원리 좀 이해해
int end = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
a.get(start).add(new dNode(end, time));
reverse.get(end).add(new dNode(start, time));
in[end]++;
}
// 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시
StringTokenizer st = new StringTokenizer(br.readLine());
int startDosi = Integer.parseInt(st.nextToken());
int endDosi = Integer.parseInt(st.nextToken());
// 위상 정혛
Queue<Integer> q = new LinkedList<>();
q.offer(startDosi);
int[] result = new int[node + 1];
while (!q.isEmpty()) {
int now = q.poll();
for (dNode next : a.get(now)) {
in[next.targetNode]--;
result[next.targetNode] =
Math.max(result[next.targetNode],
result[now] + next.value);
if (in[next.targetNode] == 0) {
q.offer(next.targetNode);
}
}
}
// 위상 정렬 reverse
int count = 0;
boolean visited[] = new boolean[node + 1];
q = new LinkedList<>();
q.offer(endDosi);
visited[endDosi] = true;
while (!q.isEmpty()) {
int now = q.poll();
for (dNode next : reverse.get(now)) {
// 1분도 쉬지 않는 도로 체크
if (result[next.targetNode] + next.value == result[now]) {
count++;
if (visited[next.targetNode] == false) {
visited[next.targetNode] = true;
q.offer(next.targetNode);
}
}
}
}
System.out.println(result[endDosi]);
System.out.println(count);
}
}
class dNode {
int targetNode;
int value;
dNode(int targetNode, int value) {
this.targetNode = targetNode;
this.value = value;
}
}
Idea
개어렵 ㅁㅊ
이들이 출발 도시에서 출발한 후 도착 도시에서 만나기까지 걸리는 최소 시간과, 1분도 쉬지 않고 달려야 하는 사람들이 지나는 도로의 수.
reference
Last updated
