문제 링크: https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 그래프 탐색, 위상 정렬 도착 도시에 가장 마지막에 도착하는 시간은 해당 도시로 들어오는 모든 출발 도시들이 도착한 시점입니다. 이를 모든 도시에 대해 순차적으로 고려하면 DAG이기 때문에 위상 정렬로 답을 구할 수 있습니다. 도로를 지나는 횟수를 계산하기 위해 역방향 간선을 추가로 입력 받아 도착 도시에서 BFS를 수행합니다. 만약 u에서 v로 이동하는데 ..

문제 링크: https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 기본적인 위상정렬 알고리즘으로 최단거리를 갱신하면 되는데 주의할 점이 하나 있습니다. indegree가 0이 되는 건물을 큐에 삽입하면서 최단거리를 갱신할 때 바로 직전 노드로만 판단하면 안 됩니다. 위와 같은 상황에서 1번 정점을 처리하고 2번 정점을 처리할 때 3번 정점의 indegree가 0이 되어서 3번 정점을 큐에 넣고 바로 직전 노..

문제 링크: https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 기본적인 위상정렬 알고리즘으로 최단거리를 갱신하면 되는데 주의할 점이 하나 있습니다. indegree가 0이 되는 건물을 큐에 삽입하면서 최단거리를 갱신할 때 바로 직전 노드로만 판단하면 안 됩니다. 위와 같은 상황에서 1번 정점을 처리하고 2번 정점을 처리할 때 3번 정점의 indegree가 0이 되어서 3번 정점을 큐에 넣고 바로 직전 노..

문제 링크: https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 그래프, 위상 정렬 위상 정렬 알고리즘을 그대로 적용하면 되는 문제입니다. 1. indegree가 0인 정점을 모두 큐에 넣는다. 2. 큐가 빌 때까지 다음을 반복한다. 3. 큐에서 정점을 하나 꺼낸다. 4. 꺼낸 정점을 결과 리스트에 넣고 정점의 인접 리스트를 확인한다. 5. 꺼낸 정점과 연결된 다른 정점의 in..