위상정렬

https://www.acmicpc.net/status?group_id=13709 채점 현황 www.acmicpc.net 풀이 건물을 짓기 위해서는 선행으로 지어져야하는 건물이 존재한다. - 위상정렬 알고리즘을 적용해야함을 알 수 있다. 위상정렬 알고리즘: https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.com 코드 # 1516번 게임개발 import sys from collections import deque n = int(sys.stdin.r..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 문제를 읽고나서 위상정렬 알고리즘임을 어렵지않게 알 수 있었다. 최소 건설 시간을 측정하기 위해 다이내믹 프로그래밍을 사용할 것이다. 건물 완성까지의 최소 시간을 구하기 위해서는 다음과 같은 말이 성립된다. - 선행 건설 되어야하는 건물이 존재한다면 후행 건설을 실시 할 수 없다. - 이를 위해서는 선행 건설 되어야하는 건물이 모두 건설되어야 한다는 얘기이다. - 선행 건설이 없는 건물..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 조건을 다시 정리하자면 1) 문제 번호는 낮을수록 쉬운 문제이다. 최대한 쉬운 문제를 먼저 풀면서 모든 문제를 풀어야한다. 2) 최대한 쉬운 문제를 먼저 푼다는 얘기는 문제번호가 내림차순으로 풀어야하는 조건이 주어질 수 있다는 얘기이다. - 진입차수가 존재하는 노드가 있다는 얘기이다. 3) 진출차수와 진입차수가 존재하지않는 노드와 진출차수는 존재하지만 진입차수가..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 위상정렬 알고리즘은 다음과 같다. https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.com..

위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 해결할 때 사용됩니다. 위상 정렬의 전제와 조건 방향 그래프: 위상 정렬은 방향성을 가진 간선으로 이루어진 그래프에서만 수행됩니다. 사이클이 없어야 함: 위상 정렬을 수행할 그래프는 순환이 없어야 합니다. 순환이 있는 경우, 어떤 노드를 먼저 방문해야 하는지 정할 수 없기 때문입니다. 위상 정렬 설명 진입 차수 계산: 각 노드의 진입 차수(들어오는 간선의 수)를 계산합니다. 진입 차수가 0인 노드 찾기: 진입 차수가 0인 노드를 찾고 큐에 넣습니다. 이 노드들은 의존성이 없는 작업이므로 먼저 수행될 수 있습니다. 노..