위상정렬 (5) 썸네일형 리스트형 [백준]3665 최종순위(Python) https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 문제 접근 5번과 3번의 상대적인 순위 관계가 바뀐다면, 5번그래프에 3번을 빼주어야 하고 3번 그래프에 5를 넣어주어야 한다. => 3번으로 들어오는 간선이 하나 줄어들고, 5번으로 들어오는 간선이 하나 늘어났으므로 차수(indegree)도 변경 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력 한 번에 2개 이상의 원소가 들어간다는 것은 진입차수가 0.. [백준]1766 문제집(Python) https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 접근 선행 문제를 풀어야 후행 문제를 풀 수 있다는 점에서 위상정렬 알고리즘을 사용해야한다. 하지만 답이 여러 개인 경우에는 아무거나 출력한다는 조건이 없기에 정답은 하나이다. 이 문제의 조건에서는 "가능한 쉬운 문제부터 풀어야 한다"라는 조건이 있다. 코드 from collections import deque import sys import heapq inpu.. [백준]1005 ACM Craft(Python) https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 접근 시도1. (실패) 어제와 정리한 위상정렬 함수를 변형해서 작성하였다. 1. 건물의 건설 시간을 담을 리스트를 인덱스에 대응시켜서 만든다. 2. 특정 건물(W)까지 짓는데 걸리는 시간을 total_cost라는 변수에 누적해서 결과로 출력한다. => 예제 1 출력 결과: 121 52 수정(성공) 코드 시도1 from collections import deque import sys in.. 위상정렬 개념 방향 그래프의 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 알고리즘 수행 과정 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 진입차수(Indegree): 특정한 노드로 '들어오는' 간선의 개수 (= 나를 가리키는 화살의 개수) 코드 from collections import deque import sys input = sys.stdin.readline # 노드, 간선 개수 v,e = map(int, input().split()) # 모든 노드에 대한 진입차수는 0으로 초기화 indegree = [0] * (v+1) # 각 노드에 연결된 .. [백준]2252 줄세우기(Python) 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://yoonstudy-diary.tistory.com/45 위상정렬 개념 방향 그래프의 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 알고리즘 수행 과정 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 yoonstudy.. 이전 1 다음