[WEEK03] 24일차. 그래프 수정, 임계경로

백준 1432 그래프 수정

예시로 주어지는 그래프를 위상정렬 했을 때 오름차순으로 숫자가 나오게끔 수정해야하는 문제다.

첫 번째로 주어지는 예제 입력은 위 그림과 같다.
V1에서 V2로 연결된 간선이 있다면, V2의 번호는 V1보다 커야 한다. 라는 조건을 만족하기 위해서는 위상정렬을 했을 때 오름차순으로 숫자가 나오게 그래프를 수정하면 된다.
수정 결과는 다음 그림과 같다.

1 2 3 5 4 (예제 입력) -> 1 2 5 3 4 (예제 출력)

답이 여러 개일 경우에는 사전 순으로 제일 앞서는 것을 출력한다.

이 때 주의할 점은 indegree를 사용하는 것이 아니라 간선의 방향을 뒤집어서 outdegree를 쓰고 최대힙을 사용해야한다는 것이다.

우선 순위가 낮은 것을 먼저 정렬하고 우선 순위가 높은 것을 정렬해야 원하는 결과를 얻을 수 있기 때문이다.

우선순위 높은 것부터 정렬
1. A2 A3 B1 (알파벳 정렬)
2. B1 A2 A3 (숫자 정렬)

우선순위 낮은 것부터 정렬
1. B1 A2 A3 (숫자 정렬)
2. A2 A3 B1 (알파벳 정렬)

코드

from heapq import *
import sys
input = sys.stdin.readline

def topology_sort(N):
    q = []
    for i in range(1, N+1):
        if degree[i] == 0:
            heappush(q, -i)

    while q:
        now = -heappop(q)
        ans[now] = N
        for i in graph[now]:
            degree[i] -= 1
            if degree[i] == 0:
                heappush(q, -i)
        N -= 1

N = int(input())
graph = [[] for _ in range((N+1))]
degree = [0] * (N+1)
ans = [0] * (N+1)

for v in range(1, N+1):
    tmp = [0] + list(map(int, input().strip()))
    for i in range(1, N+1):
        if tmp[i] == 1:
            graph[i].append(v)
            degree[v] += 1

topology_sort(N)

if ans.count(0) > 1:
    print(-1)
else:
    print(*ans[1:])

백준 1948 임계경로

문제 링크

벨로그 글을 참고하였다.

최장 시간이 걸리는 경로의 시간과, 최장 시간이 걸리는 경로에 속하는 모든 도시의 수를 출력해야하는 문제다.

위상정렬을 사용해 가장 오래 걸리는 시간의 경로를 계속 갱신해주고, 같은 시간이 걸리는 최장 시간 경로도 체크해준다.
위상정렬을 하는동안 직전 경로를 back이라는 리스트에 담아주는데, 마지막에 bfs를 돌리면서 최장 시간이 걸리는 경로의 모든 도시들을 체크해서 route라는 집합에 담아준 다음 길이를 출력한다.

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
M = int(input())

indegree = [0] * (N+1)
graph = [[] for _ in range(N+1)]
back = [[] for _ in range(N+1)]

for _ in range(M):
    # a: 출발 도시, b: 도착 도시, c: 걸리는 시간
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    indegree[b] += 1

start, end = map(int, input().split())

q = deque([])
q.append(start)

time = [0] * (N+1)

while q:
    # now: 도시, back: 직전 경로(경로 추적 위함)
    now = q.popleft()

    for (next, cost) in graph[now]:
        indegree[next] -= 1
        if indegree[next] == 0:
            q.append(next)
        if time[next] < time[now] + cost:
            # 더 오래 걸리는 걸로 갱신
            time[next] = time[now] + cost
            # 직전 경로도 갱신
            back[next] = [now]
        # 시간이 같을 경우(같은 시간 경로 여러개일 경우), 추가함.
        elif time[next] == time[now] + cost:
            back[next].append(now)

q = deque([end])
route = set()
while q:
    now = q.popleft()
    for nx in back[now]:
        if (now, nx) not in route:
            route.add((now, nx))
            q.append(nx)

print(time[end])
print(len(route))