a -> b 방향으로 화살표가 있다면 a가 작업된 후에 b를 작업할 수 있다는 이야기 edge[a]에는 b를 추가해주고 cnt[b]는 1증가시킨다. (b로 들어오는 간선개수라고 생각해준다) 사전작업(간선)이 없는 곳, 즉 cnt[해당작업번호]=0인 곳부터 출력해준다. dfs의 경우는 방문 배열 처리를 해준다. bfs는 0인 곳을 큐에 먼저 다 넣어줄 수 있어서 필요없다. 현재 방문한 곳 cur와 연결된 곳의 간선의 수를 하나 줄여주고 (사전작업이 하나 줄었으니까!) 연결된 곳의 cnt[다음정점번호]가 0이 된다면 방문할 수 있다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include #include using namespace std;..
from collections import defaultdict import heapq hour=defaultdict(int) order=defaultdict(list) cnt=defaultdict(int) n=int(input()) for i in range(1,n+1): m=list(map(int,input().split())) hour[i]=m[0] if m[1]==-1: continue for j in m[1:-1]: order[j].append(i) # i이전에 j가 성행한다 cnt[i]+=1 q=[] ans=[0]*(n+1) for i in range(1,n+1): if cnt[i]==0: q.append(i) ans[i]=hour[i] while q: x=q.pop() for y in ord..
height: 현재 번호 작업을 하기 위한 우선순위 작업들을 담고 있다 cost: 현재 작업의 비용(시간) 모든 작업을 돌면서 현재 번호를 작업하기 위해 먼저 해야할 작업들의 비용의 최대값(여러 작업을 동시에 할 수 있다는 조건이 있다)에 현재 작업의 시간을 더한 것이 현재 번호를 작업하는 걸리는 시간이다 from collections import defaultdict import heapq height=defaultdict(list) cost=defaultdict(int) n=int(input()) for i in range(1,n+1): c=list(map(int,input().split())) cost[i]=c[0] if c[1]==0: continue for j in c[2:]: height[i]..
위상정렬 + 우선순위큐 문제번호가 작은 것 부터 풀어야된다 from collections import defaultdict import heapq height=defaultdict(list) cnt=defaultdict(int) q=[] n,m=map(int,input().split()) for i in range(m): a,b=map(int,input().split()) height[a].append(b) cnt[b]+=1 # b이전에 a가 선행된다 for i in range(1,n+1): if cnt[i]==0: q.append(i) result=[] while q: x=heapq.heappop(q) result.append(x) for j in height[x]: cnt[j]-=1 if cnt[j]..
from collections import defaultdict from collections import deque height=defaultdict(list) cnt=defaultdict(int) dq=deque() n,m=map(int,input().split()) for i in range(m): a,b=map(int,input().split()) height[a].append(b) cnt[b]+=1 # b이전에 a가 선행된다 for i in range(1,n+1): if cnt[i]==0: dq.append(i) result=[] while dq: x=dq.popleft() result.append(x) for j in height[x]: cnt[j]-=1 if cnt[j]==0: dq.appe..