🧚알고리즘🧚-그래프- 위상 정렬

🧚위상 정렬🧚

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

시간 복잡도 : O(노드 수 + 에지 수)

 

사이클이 존재하면 안 됨 -> 노드 간의 순서를 명확하게 정의할 수 없기 때문

위상 정렬이 늘 같은 정렬 결과를 보장하지는 않음(위상이 같은 노드가 존재할 시)

 

진입 차수(in-degree) : 자기 자신을 가르키는 에지의 개수

 

1. 인접 리스트를 만든 후 이를 이용해 진입 차수 리스트를 만든다.
2. 진입 차수가 0인 노트를 선택하고
->  선택된 노드를 결과 리스트에 저장 / 인접 리스트에서 선택된 노드들의 진입 차수를 1씩 빼기
3. 모든 노드가 정렬될 때까지 2 반복하기. (0이 생기지 않는 경우 없음)

---

🥇골드 3

2252번: 줄 세우기

근본

from collections import deque
from sys import stdin
N, M = map(int, stdin.readline().split())
Nlist = [[] for _ in range(N+1)] #인접리스트
inDegree = [0 for _ in range(N+1)] #진입차수

for _ in range(M):
    a, b = map(int, stdin.readline().split())
    Nlist[a].append(b) # 인접 리스트 저장 (방향 O)
    inDegree[b] += 1 # 진입 차수 데이터 저장

# 큐 선입선출==위상정렬 굿  
MyQueue = deque()
for i in range(1,N+1):
    if inDegree[i] == 0: # 진입 차수 == 0 노드 큐 저장
        MyQueue.append(i)

# 큐 pop => 탐색결과 append, 해당 노드의 인접 노드 진입 차수 --
while(MyQueue):
    nowNode = MyQueue.popleft()
    print(nowNode, end = ' ')
    for cha in Nlist[nowNode]:
        inDegree[cha] -= 1
        if inDegree[cha] == 0:
            MyQueue.append(cha)

---

🥇골드 3

1516번: 게임 개발

분기가 갈라지므로 시간 계산을 어떻게 해야 하나 했는데

리스트 하나를 새로 만들어서 이전 부모 노드(nowNode)의 시간 + 지금 노드(cha) 로 저장했다.

from collections import deque
from sys import stdin
N= int(stdin.readline())
Nlist = [[] for _ in range(N+1)] #인접리스트
inDegree = [0 for _ in range(N+1)] #진입차수
result = [0 for _ in range(N+1)] #시간
reresult =[] #순서

for i in range(1,N+1):
    nlist = list(map(int, stdin.readline().split()))[0:-1]
    result[i] = nlist[0] #자체 시간
    for j in range(len(nlist)-1):
        Nlist[nlist[j+1]].append(i)
    inDegree[i] += len(nlist)-1 

MyQueue = deque()
for i in range(1,N+1):
    if inDegree[i] == 0: 
        MyQueue.append(i)

while(MyQueue):
    nowNode = MyQueue.popleft()
    reresult.append(nowNode)
    for cha in Nlist[nowNode]:
        inDegree[cha] -= 1
        result[cha] += result[nowNode]
        if inDegree[cha] == 0:
            MyQueue.append(cha)

for cha in reresult:
    print(result[cha])

????????

글 읽기 - 에엥 대체 왜 출력 초과가 나는 건가요..??

아 이런.. 사이클은 없지만^^ 경로는 여러개 있을 수 있기 때문에 부모 노드가 여러개 생길 수도 있다는 걸 알았어야지..

GG

책을 보도록 하겠다.

앗

새로운 아이디어가

경로가 여러개라면 개중 가장 큰 것이 답이 된다. 결과 리스트를 하나 더 만들어보자

from collections import deque
from sys import stdin
N= int(stdin.readline())
Nlist = [[] for _ in range(N+1)] #인접리스트
inDegree = [0 for _ in range(N+1)] #진입차수
result = [0 for _ in range(N+1)] #건설기본시간
reresult =[] #순서
finalresult = [0 for _ in range(N+1)] #찐

for i in range(1,N+1):
    nlist = list(map(int, stdin.readline().split()))[0:-1]
    result[i] = nlist[0] #자체 시간
    for j in range(len(nlist)-1):
        Nlist[nlist[j+1]].append(i)
    inDegree[i] += len(nlist)-1 

MyQueue = deque()
for i in range(1,N+1):
    if inDegree[i] == 0: 
        MyQueue.append(i)
        finalresult[i] = result[i]

while(MyQueue):
    nowNode = MyQueue.popleft()
    reresult.append(nowNode)
    for cha in Nlist[nowNode]:
        inDegree[cha] -= 1
        finalresult[cha] = max(finalresult[cha],finalresult[nowNode]+result[cha])
        if inDegree[cha] == 0:
            MyQueue.append(cha)

for cha in reresult:
    print(finalresult[cha])

앗 이번엔 틀렸다!

이젠 안해

답지 본다

잠깐..

이거 출력을..건축순서 상관 없이 그냥 숫자크기대로 출력하는 거였나?

..

for i in range(1,N+1):
    print(finalresult[i])

마지막 이렇게 하면 맞았다

쓸데없는짓을햇군...

하필 테케 답 건축순서가 숫자크기순일건 뭐람 

---

✳️ 플래티넘 5

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: # 위상 정렬 reverse 수행
    now = queue.popleft()
    for next in reverseA [now]:
        # 1분도 쉬지 않는 도로 체크
        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)

<에지 뒤집기> 아이디어 

: 에지의 방향이 반대인 역방향 인접 리스트 저장해서 이용

 

임계 경로 : 여러 가지 경로 중에서 가장 긴 시간이 걸리는 경로

(도착 도시의 임계 경로값이 만나는 시간이 됨)

(역방향 위상 정렬 수행 중 "해당 도시의 임계 경로값 + 도로시간(에지) == 이전 도시의 임계 경로값"일 경우 가 1분도 쉬지 않고 가야 하는 도로)

왜????

왜>?>???>이해 ㄴ

 

도착지점으로부터 "백트래킹" 하는 거래