위상정렬 (2) 썸네일형 리스트형 [백준] 1613번 : 역사 1613번: 역사 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 🤔 문제분석 위상정렬과 플로이드 워셜로 풀 수 있는 문제입니다. 저는 처음에 문제를 풀때 위상정렬로 접근하였습니다. 위상정렬을 할때에 **부모노드를 자식노드에 업데이트(부모노드는 자식노드에게 내가 너보다 먼저 야 라고 표시)**하면서 자기자신을 방문할때 자기자신을 추가하면 됩니다. 💻 코드 import sys input = sys.stdin.readline INF = sys.maxsize n, k = map(int, input().spl.. [백준] 2056번 : 작업 2056번: 작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 🤔 문제분석 위상정렬을 알고 있다면 해당문제를 쉽게 풀 수 있다. 위상정렬을 간단하게 설명하자면, 진입차수를 입력받아 진입차수가 0일때만 방문하도록한다. 여기서 방문할때에 기존에 걸렸던 시간중 가장 큰 시간을 가져와서 가중치에 더하면 된다. 문제에서 선행관계에 있는 작업이 하나도 없는 작업이 하나 이상 존재함으로 처음 루트를 방문 할때에 진입차수가 0인 루트가 여러개가 있다는 말임으로, 초기 진입차수가 0인 루트를 찾아서 모두 방문 해.. 이전 1 다음