728x90 반응형 위상정렬3 2623번: 음악프로그램 (위상정렬) https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다. 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD.. 2022. 8. 10. 백준 14567번: 선수과목 (위상정렬) https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 문제 올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 .. 2022. 8. 9. 8. 기타 그래프 이론: 위상 정렬 위상정렬은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는'것임 사이클이 없는 방향그래프(DAG:Direct Acycle Graph) 에서 위상정렬 하는 방법 설명. 1. 진입차수가 0인 노드를 큐에 넣는다 2. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 이것을 큐가 빌 때까지 반복한다 만약 그래프에 사이클이 존재한다면.. 사이클에 포함되는 노드는 진입차수가 모두 1이상이 되므로 큐에 들어가지 못하고 정렬이 끝날것이다 from collections import deque v,e=map(int,input().split()) indegree=[0]*(v+1) graph=[[]for i in range(v+1)] for i in range(e): a,b=ma.. 2022. 8. 8. 이전 1 다음 728x90 반응형