[ 위상 정렬 ] 알고리즘

 

1. 개념

 

위상 정렬 : 방향성(선후 관계)을 유지하면서 순서대로 나열하는 것    ex) 대학교 선수 과목 구조

전체적인 순서가 고정되어 있진 않지만 정해진 방향성을 지키면서 순서를 나열해야 하는 것이다

위상 정렬의 결과는 유일하지 않다

 

위상 정렬은 사이클이 없는 방향 그래프를 이용한다

 

시간 복잡도는 O(V+E)  -> V : 노드 수, E : 에지 수

 

 

2.  위상 정렬 구현

 

    ( 1 )  초기 설정

           - 인접 리스트 생성

           - 진입 차수 리스트 생성

              진입 차수란 자기 자신을 가리키는 에지의 개수를 의미한다

 

    ( 2 )  진입 차수가 0인 노드를 선택하고 선택된 노드 정렬 리스트에 저장

    ( 3 )  선택된 노드의 인접 노드들의 진입 차수 1씩 빼기

    모든 노드가 정렬될 때까지 ( 2 ) ~ ( 3 ) 반복하기

 

 

 

3.  문제

 

# 1  줄 세우기 - 백준 2252번

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

import sys
from collections import deque
input = sys.stdin.readline


queue = deque()
n, m = map(int, input().split())
node = [[] for _ in range(n+1)]  # 인접 리스트
indegree = [0 for _ in range(n+1)] # 접근 차수 리스트
numList= [] # 정렬 리스트


# 인접 리스트, 접근 차수 리스트 생성
for i in range(m):
    a, b = map(int, input().split())
    node[a].append(b)
    indegree[b] += 1

# 접근 차수가 0인 노드 큐에 삽입
for i in range(len(indegree)):
    if indegree[i] == 0:
        if i!= 0:
            queue.append(i)

# 큐가 빌 때까지
while queue:
    a = queue.popleft() # 큐에서 데이터 pop
    numList.append(a) # pop한 데이터 정렬 리스트에 삽입
    # 인접 노드의 접근 차수 1 빼기
    for i in node[a]: 
        indegree[i] -= 1
        # 접근 차수가 0 되면 큐에 삽입
        if indegree[i] == 0:
            queue.append(i)

for i in range(len(numList)):
    print(numList[i], end = ' ')

 

 

 

 

# 2  게임 개발 - 백준 1516번

https://www.acmicpc.net/problem/1516

1516번: 게임 개발

 

import sys
from collections import deque

input = sys.stdin.readline


n = int(input())
selfTime = []  # 해당 건물을 짓는 데에 걸리는 시간
indegree = [0 for _ in range(n+1)]  # 접근 차수 리스트 생성
node = [[] for _ in range(n+1)]  # 인접 리스트 생성

queue = deque()
array = []  # 정렬 리스트

# 먼저 지어져야 하는 건물이 다 지어지는 데에 걸리는 시간
ans = [0 for _ in range(n+1)]  


for i in range(n):
    info = list(map(int, input().split()))
    selfTime.append(info.pop(0))
    cnt = 0
    while True:
        a = info.pop(0)
        if a == -1:
            break
        node[a].append(i+1)
        cnt += 1
    indegree[i+1] += cnt 

# 접근 차수가 0인 노드 큐에 삽입
for i in range(1, n+1):
    if indegree[i] == 0:
        queue.append(i)

# 위상 정렬, ans 업데이트
while queue:
    a = queue.popleft()
    array.append(a)
    for i in node[a]:
        indegree[i] -= 1  # 인접 노드의 접근 차수 1 빼기
        # ans에 들어가는 값은 선수 건물이 다 지어지는 데 걸리는 시간을 의미한다
        # 위의 설명대로 생각하면 ans값 = 현재 건물(노드)의 선수 건물(노드)이 지어지는 데 걸리는 총 시간
        # 하지만 이미 현재 건물(노드)의 ans값이 윗줄에서 설명한 값보다 크다면 현재 ans값을 유지하면 된다
          (건물은 여러개 동시에 지어질 수 있기 때문)
        ans[i] = max(ans[i], ans[a] + selfTime[a-1])
        if indegree[i] == 0:
            queue.append(i)

# 건물이 지어지는 데에 걸리는 총 시간 ( 먼저 지어져야 하는 건물이 다 지어지는 데 걸리는 시간 + 해당 건물을 짓는 데 걸리는 시간
for i in range(n):
    print(selfTime[i] + ans[i+1])

 

 

이 문제는 풀이 방법을 생각하는 데에 애를 많이 먹었는데 

결국은 교재와 세으니의 설명과 블로그글을 보고나서 마침내 이해했다

 

이 문제는 

1. 건물 건축의 선후 관계를 파악한 뒤에 위상 정렬 (처음에 접근 차수도 이상하게 구해버림....)

2. 건물이 지어지는 데 걸리는 총 시간 = 선수 건물이 다 지어지는 데 걸리는 시간 + 해당 건물을 짓는 데 걸리는 시간

3. 건물은 동시에 여러 개 지어질 수 있다는 조건

 

이 세가지를 잘 생각하면서 풀어야 한다

 

위상 정렬을 구현할 때 선후 관계를 잘 파악하는 게 중요한 것 같다

선 -> 후 를 따져서 '후'에 해당하는 노드의 접근 차수를 증가시키면 된다

 

 

 

 

# 3  임계경로 - 백준 1948번

https://www.acmicpc.net/problem/1948

1948번: 임계경로

 

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
M = int(input())
A = [[] for _ in range(N+1)]
reverseA = [[] for _ in range(N+1)]
indegree = [0] * (N+1)

for i in range(M):
    S,E,V = map(int, input().split())
    A[S].append((E,V))
    reverseA[E].append((S,V))
    indegree[E] += 1
    
startDosi, endDosi = map(int, input().split())

queue = deque()
queue.append(startDosi)
result = [0]*(N+1)

while queue:
    now = queue.popleft()
    for next in A[now]:
        indegree[next[0]] -= 1
        result[next[0]] = max(result[next[0]], result[now] + next[1])
        if indegree[next[0]] == 0:
            queue.append(next[0])

resultCount = 0
visited = [False] * (N+1)
queue.clear()
queue.append(endDosi)
visited[endDosi] = True

while queue:
    now = queue.popleft()
    for next in reverseA[now]:
        if result[next[0]] + next[1] == result[now]:
            resultCount += 1
            if not visited[next[0]]:
                visited[next[0]] = True
                queue.append(next[0])

print(result[endDosi])
print(resultCount)

 

출력해야 하는 값

- 출발 도시부터 도착 도시까지의 최장 경로( 간선의 가중치 합이 가장 큰 경로 )를 지나는 데 걸리는 시간

- 최장 경로에 포함되는 간선의 개수

 

a.  최장 경로를 지나는 데 걸리는 시간

     위상 정렬을 통해 출발 도시부터 현재 노드까지 걸리는 최대 시간을 누적해 출발 도시부터 도착 도시까지의 최대 시간을 구한다 

     

     최대 시간 = max(현재 노드에 저장된 시간, 이전 노드에 저장된 시간 + 이전 노드 ~ 현재 노드 걸리는 시간)

     이걸 누적해서 구하다보면 출발 도시부터 각 도시까지의 최대 시간이 모두 나오게 된다

     (최장 경로를 지나는 데 걸리는 시간 또한 당연히 나오게 된다)

 

그래프를 뒤집어서 ( 간선의 방향을 뒤집기 ) a를 한번 더 반복해준다

-> 도착 노드부터 각 노드까지의 최대 시간이 나온다

 

b. 최장 경로에 포함되는 간선의 개수

    최장 경로에 포함되는 간선은 bfs를 이용해 각 노드를 방문하면서

    방금 지나온 간선(현재 노드를 방문하기 위해)이 최장 경로에 포함되는지 하나씩 탐색할 것이다

 

    간선이 최장 경로에 포함되는지 판별하기 위한 조건

    A : 출발 노드부터 현재 노드까지의 최대 시간 + 도착 노드부터 현재 노드까지의 최대 시간 == 출발 노드부터 도착 노드까지의 최대 시간

    -> 현재 노드를 거치는 최장 경로가 있는가

    B : 출발 노드부터 이전 노드까지의 최대 시간 + 이전 노드부터 현재 노드까지 걸린 시간 == 출발 노드부터 현재 노드까지의 최대 시간

    -> 이전 노드 - 현재 노드 간선이 출발 노드부터 현재 노드까지의 최장 경로에 포함되는가

 

  이 두 조건을 만족하면 이전 노드 - 현재 노드 간선을 최장 경로에 포함된 간선으로 인정할 수 있다

 

 

우와 이 문제 교재 보고서도 이해가 안 돼서 블로그 글 보면서 이해했다....

으아아아 좀 더 수련해서 다음엔 내가 직접 뿌신다아아악

 

 

참고한 블로그 글 ( 백준 1948 )

https://seongmok.com/14

C++ 백준 1948 (임계경로)