코드 # 유향 비순환 그래프, 길 정렬 -> 위상정렬 사용 # 갈 수 있는 곳의 비용을 하나 하나 다 따져주어야 한다 # 때문에 진입차수가 0이 아니더라도 비용 최신화 from collections import deque import sys input = sys.stdin.readline def topol_sort(): queue = deque([1]) # 1부터 시작 while queue: pn = queue.popleft() for i in graph[pn]: indegree[i[0]] -= 1 # 진입차수 -1 cost = visited[pn]+i[1] if cost > visited[i[0]]: visited[i[0]] = cost chase[i[0]] = pn # 가장 높은 값으로 초기화될 때 ..
위상정렬
코드 from collections import deque import sys input = sys.stdin.readline n = int(input()) graph = [[] for _ in range(n+1)] indegree = [0] * (n+1) time = [0]*(n+1) visited = [0]*(n+1) for i in range(1,n+1): list = [*map(int,input().split())] time[i] = list[0] indegree[i] = list[1] if len(list) > 2: for j in list[2:]: graph[j].append(i) def topol_sort(): queue = deque() for i in range(1,n+1): if ind..
코드 from collections import deque import sys input = sys.stdin.readline n,m = map(int, input().split()) graph = [[] for _ in range(n+1)] indegree = [0]*(n+1) for i in range(1,m+1): lst = [*map(int, input().split())] for j in range(1,lst[0]): graph[lst[j]].append(lst[j+1]) indegree[lst[j+1]] += 1 def topol_sort(): queue = deque() sequence = [] for i in range(1, n+1): if indegree[i] == 0: queue.app..
코드 # 선수문제, 위상정렬로 하되 큐에 들어가는 값에 우선순위가 있다. # 큐를 이용할 때 우선순위가 생기면 우선순위 큐를 사용한다. # 여기서는 앞에 문제가 뒤에 문제보다 쉽기 때문에 우선순위 큐를 사용해준다. import sys, heapq input = sys.stdin.readline n,m = map(int, input().split()) graph = [[] for _ in range(n+1)] indegree = [0]*(n+1) for _ in range(m): x,y = map(int, input().split()) graph[x].append(y) indegree[y] += 1 def topol_sort(): solve = [] queue = [] for i in range(1, n+..
코드 import sys from collections import deque input = sys.stdin.readline n = int(input()) # 노드 m = int(input()) graph = [[] for _ in range(n+1)] indegree = [0]*(n+1) res = [0]*(n+1) for _ in range(m): x,y,k = map(int, input().split()) # x 완성, y 기본, k 필요한 개수 graph[x].append((y,k)) indegree[y] += 1 res[n] = 1 origin = [] # 기본 부품을 넣어줄 리스트 def topological_sort(): queue = deque([n]) for i in range(1, n..
코드 # 선수과목에는 사이클이 생길 수 없다. 따라서 유향 비순환 그래프이다. # 몇 학기 째에 들을 수 있는지 확인해야하므로 위상정렬 이용 import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().split()) graph = [[] for _ in range(n+1)] indegree = [0]*(n+1) # 전입차수 visited = [0]*(n+1) # 학기 기록용 방문리스트 for _ in range(m): x,y = map(int, input().split()) graph[x].append(y) indegree[y]+=1 def topol_sort(): queue = deque() for i..
코드 # 키순서는 사이클이 생길 수 없다. # 따라서 유향 비순환 그래프라고 할 수 있다 # 정렬을 해주어야 하므로 위상정렬을 사용하면 된다. import sys from collections import deque input = sys.stdin.readline def topol_sort(): queue = deque() for i in range(1,n+1): if indegree[i] ==0: # 전입차수가 0인 값을 큐에 삽입 queue.append(i) while queue: popnum = queue.popleft() for j in graph[popnum]: indegree[j] -= 1 # 전입차수 하나 삭제 if indegree[j] == 0: # 전입차수가 0인 값을 큐에 삽입 queu..
코드1 # BFS로 해결 import sys from collections import deque input = lambda: sys.stdin.readline().rstrip() # 람다함수로 사용 tc = int(input()) def bfs(s,g,v,t): queue = deque([s]) v[s] = t[s] endpoint = [] # 끝에 도달한 값을 모아줄 리스트 while queue: popnum = queue.popleft() if g[popnum]: # 올라갈 값이 있는 경우 for i in g[popnum]: if v[i] < v[popnum]+t[i]: # 큰값으로 초기화 v[i] = v[popnum]+t[i] queue.append(i) else: endpoint.append(p..
