[위상정렬] 1005번, 14567번

1. 선수과목

링크 - https://www.acmicpc.net/problem/14567

코드

from collections import deque
import sys

input = sys.stdin.readline

#노드 간선 입력
v,e = map(int,input().split())

#진입차수, 학기수 리스트
indegree=[0]*(v+1)
total = [1]*(v+1)

#그래프
graph = [[] for i in range(v+1)]

#입력받기
for _ in range(e):
    a,b = map(int, input().split())
    indegree[b]+=1 #진입차수 +1
    graph[a].append(b)

def topology_sort():
    q = deque()
    
    #진입차수 0인 노드 넣기
    for i in range(1,v+1):
        if indegree[i]==0:
            q.append(i)
    
    #탐색
    while q:
        now = q.popleft()
        for i in graph[now]:
            indegree[i]-=1 #간선 끊기
            if indegree[i]==0:
                total[i] = total[now]+1
                q.append(i)

topology_sort()

for t in total[1:]:
    print(t, end=" ")

순서가 정해져있기 때문에 위상정렬을 사용해야 했고, 노드를 큐에서 뺄 때 선수과목의 학기수+1을 해주었다.

2. ACM Craft

링크 - https://www.acmicpc.net/problem/1005

코드

from collections import deque
import sys

input = sys.stdin.readline

#노드 간선 입력
v,e = map(int,input().split())

#진입차수, 학기수 리스트
indegree=[0]*(v+1)
total = [1]*(v+1)

#그래프
graph = [[] for i in range(v+1)]

#입력받기
for _ in range(e):
    a,b = map(int, input().split())
    indegree[b]+=1 #진입차수 +1
    graph[a].append(b)

def topology_sort():
    q = deque()
    
    #진입차수 0인 노드 넣기
    for i in range(1,v+1):
        if indegree[i]==0:
            q.append(i)
    
    #탐색
    while q:
        now = q.popleft()
        for i in graph[now]:
            indegree[i]-=1 #간선 끊기
            if indegree[i]==0:
                total[i] = total[now]+1
                q.append(i)

topology_sort()

for t in total[1:]:
    print(t, end=" ")

처음에 예제1번의 2번째 입력의 답이 19라고 생각을 했다.
그래서 문제 잘못된거 아냐? 했는데, 역시~ 잘못된 건 나였다ㅎ

문제에서 건물 건설이 동시진행이 가능하다고 적혀있었다.

7번 건물을 짓기 위해서는 1->2,3->5,6->7의 순서로 진행이 되야 한다.
5번에서 간선을 제거했어도 6->7간선이 존재하기 때문.

그래서 10+20+8+1인 39초가 답이 되는거였다~

deep copy

이전 글 링크 - https://velog.io/@isg/파이썬-리스트-다루기

이전에도 정리했듯이 python에서는 = 연산이나 copy모듈의 copy연산을 하면 값이 같이 바뀌게 된다.
값만 복사를 한 다른 객체를 만들고 싶다면 deepcopy 함수를 사용해야 한다.