Dev_Diary

https://www.acmicpc.net/problem/14567역시 전형적인 위상정렬 문제입니다.위상정렬 리스트를 만들어 순회를 하되, 순회가 가능해도 한번에 순회하는 것이 아닌 학기마다 끊어서 가능한 수업을 모두 큐에 넣어주어야 합니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, M, subjects): # 위상정렬 리스트 / [[들어오는 노드], 이수한 학기, [나가는 노드]] topol_list = [[set(), 0, set()] for _ in range(N+1)] for A, B in subjects: topol_list[A][2].add(B) top..

https://www.acmicpc.net/problem/2056전형적인 위상정렬 문제입니다.들어오는 노드와 나가는 노드를 정리해준 뒤 시간을 누적하며 들어오는 노드를 모두 탐색한 노드를 탐색하면 됩니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, works): # 위상정렬 그래프 / [[들어오는 노드들], 소요 시간, [나가는 노드들]] topol_graph = [[[], 0, []] for _ in range(N+1)] for w in range(len(works)): # 소요 시간 topol_graph[w+1][1] = works[w][0] # 입..

https://www.acmicpc.net/problem/2637위상정렬 문제입니다. 간단하게 생각해보면 DFS 나 BFS 를 사용해 한 부품씩 곱해 더해주면 될 것 같지만 단계나 부품의 수가 복잡해지고 배수가 늘어나면 시간이나 메모리가 부족해집니다. 그렇기에 조금 더 효율적으로 단계를 진행할 필요가 있습니다. 그렇기에 단계별로 개수를 병합해 한번에 곱하는 식으로 진행하면 비교적 효율적으로 진행할 수 있습니다.위 방법으로 진행할 때 모든 중간부품의 개수를 카운트하지 않았을 때 다음 단계를 계산해버리면 오류가 생기므로 중간부품의 개수가 모두 카운트 될 때 다음 단계로 넘어가야 하는데, 이 때 위상정렬을 사용할 수 있습니다. B 부품을 만들기 위해 A 부품이 필요하다고 할 때(A->B) 'B 부품 노드에 A..

https://www.acmicpc.net/problem/1516단순한 위상정렬 문제입니다. 연결 관계를 정리해준 뒤 선행 노드가 없는 노드를 시작 노드로 잡습니다.시작 노드부터 BFS 로 순회하며 걸리는 최대 시간을 기록해줍니다. 다만 큐에 다음 노드를 넣을 때는 선행 노드가 모두 방문되어야 모든 건설 시간을 고려할 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, time_list, topol_list, graph):    # 큐    dq = deque([])    # 방문 기록    visited = [False for _ in range(N+1)]    # 필요한 시간 리스트    max_..

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 백준 2252 Python https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다 dev-diary-0717.tistory.com 파이..

https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 백준 2150 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이 dev-diary-0717.tistory.com 이전의 포스트에서 위상..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬 알고리즘입니다. 다만 큐를 사용한 BFS 방식이 아닌 진입차수가 0 인 노드 하나 추가 -> 연결된 모드 노드 진입차수 -1 -> 진입차수가 0 인 노드 하나 추가 가장 작은 노드가 입력될 수 있도록 해야합니다. import sys def solution(N, M, data_list): # 위상정렬 알고리즘 # 트리, tree[i] = [[i 의 자식들], ..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬을 사용해 풀어야 하는 문제입니다. 우선 바뀐 순서를 트리에 추가하고 나머지 순서는 바뀌면 안되므로 미리 추가된 순서들을 제외하고 트리에 추가해줍니다. 그런 뒤에 위상정렬 알고리즘을 사용하면 되는데, 큐에 노드가 2개 이상 들어있다면 정확한 순서를 파악할 수 없으므로 '?' 를 출력합니다. 또 위상정렬 알고리즘을 모두 통과한 뒤에 생긴 새로운 줄에 속한 노드의 수가 전체 노드의 수와..

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 위상 정렬 알고리즘을 사용하면 풀 수 있습니다. 간단하게 설명하자면 어떤 노드를 방문하는데 조건이 있는 경우 위상정렬을 사용하게 됩니다. 특정 노드 A 를 방문할 때 B, C 를 선행 방문해야 한다고 가정하겠습니다. A와 B, A 와 C를 간선으로 연결하고, 각 노드에서의 들어오고 나가는 간선을 체크해줍니다. A : 나가는 간선 0 / 들어오는 간선 2 ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net BFS 로 풀다가는 큐와함께 속도 터져나가는 문제입니다. 위상정렬 알고리즘을 통해 큐에 진입되는 조건을 지정해줘야 풀 수 있습니다. 간단하게 설명하자면 특정 노드에서 들어가고 나가는 노드의 수를 기록해 들어가는 노드가 적은 순서로 탐색하는 알고리즘입니다. 특정 노드를 방문하는 조건이 여러 개일 때 사용하는 알고리즘입니다. from collections import deque import sy..