230829 - [Java-Python] 위상정렬

[robert-min]

BOJ.2252 줄세우기 링크

• 문제풀이
  • 위상정렬 문제로 입력값을 받을 때 입력 차수를 계산하는 indegree 리스트 구성
  • indegree[n] == 0 부터 차례대로 입력

python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

indegree = [0] * (N+1)
from collections import defaultdict
graph = defaultdict(list)

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    indegree[v] += 1

from collections import deque
result = []
def bfs():
    Q = deque()

    for i in range(1, N+1):
        if indegree[i] == 0:
            Q.append(i)

    while Q:
        now = Q.popleft()
        result.append(now)

        for nx in graph[now]:
            indegree[nx] -= 1
            if indegree[nx] == 0: Q.append(nx)

bfs()
print(*result)

java

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        input();
        solution();
    }

    static int N, M;
    static ArrayList<Integer>[] adj;
    static int[] indeg;

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        adj = new ArrayList[N+1];
        indeg = new int[N+1];

        for (int i=1; i<=N; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i=0; i < M; i++) {
            int x = scan.nextInt(), y = scan.nextInt();
            adj[x].add(y);
            indeg[y]++;
        }
    }

    static void solution() {
        Deque<Integer> queue = new LinkedList<>();

        // 제일 앞에 정렬될 수 있는 정점 indeg == 0
        for (int i=1; i <= N; i++) {
            if (indeg[i] == 0) queue.add(i);
        }

        while (!queue.isEmpty()) {
            int x = queue.poll();
            sb.append(x).append(' ');
            for (int y: adj[x]) {
                indeg[y]--;
                if (indeg[y] == 0) queue.add(y);
            }
        }
        System.out.println(sb);
    }

}

[robert-min]

BOJ.1005 ACM craft 링크

• 문제풀이
  • 위상정렬로 indegree == 0인 값부터 확인
  • 이 문제의 포인트는 탐색하는 과정에서 최대 시간을 계속 갱신해야 함!!

python

import sys
input = sys.stdin.readline

from collections import defaultdict
from collections import deque
T = int(input())

for _ in range(T):

    N, K = map(int, input().split())
    times = list(map(int, input().split()))

    graph = defaultdict(list)
    indegree = [0] * (N+1)

    for _ in range(K):
        u, v = map(int, input().split())
        graph[u].append(v)
        indegree[v] += 1

    target = int(input())

    Q = deque()
    T_done = [0] * (N+1)
    for i in range(1, N+1):
        if indegree[i] == 0:
            Q.append(i)
            T_done[i] += times[i-1]

    while Q:
        now = Q.popleft()

        max_t = 0

        for nx in graph[now]:
            indegree[nx] -= 1
            if indegree[nx] == 0:
                Q.append(nx)
            T_done[nx] = max(T_done[nx], T_done[now] + times[nx-1])

    print(T_done[target])

java

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static int[] indeg, T_done, T;
    static ArrayList<Integer>[] adj;

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        adj = new ArrayList[N+1];
        indeg = new int[N+1];
        T_done = new int[N+1];
        T = new int[N+1];
        for (int i=1; i <= N; i++) {
            adj[i] = new ArrayList<>();
            T[i] = scan.nextInt();
        }

        for (int i=0; i < M; i++) {
            int x = scan.nextInt(), y = scan.nextInt();
            adj[x].add(y);
            indeg[y]++;
        }
    }

    static void solution() {
        Deque<Integer> queue = new LinkedList<>();

        for (int i=1; i <= N; i++) {
            if (indeg[i] == 0) {
                queue.add(i);
                T_done[i] = T[i];
            }
        }

        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (int y : adj[x]) {
                indeg[y]--;
                if (indeg[y] == 0) queue.add(y);
                T_done[y] = Math.max(T_done[y], T_done[x] + T[y]);
            }
        }
        int W = scan.nextInt();
        System.out.println(T_done[W]);
    }

    public static void main(String[] args) {
        int Q = scan.nextInt();
        while (Q > 0) {
            Q--;
            input();
            solution();
        }
    }

}