위상정렬2

• 

  [백준]1005 ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을.. TIL/SW&백준 문제 리뷰 2022. 2. 24.

• 

  위상정렬 (Topological Sort) 위상정렬 (Topological Sort) 선후 관계가 정의된 그래프 구조에서 정렬하기 위해 사용 그래프가 순환 구조 가지면 사용 불가 동작 진입 차수 테이블 생성 및 진입 차수 계산 진입 차수가 0인 노드 큐에 넣기 (순서 상관 X) 큐에서 노드 꺼내 연결된 노드들 진입 차수 감소 ( -1 해준다), 진입 차수가 0이 되면 큐에 넣기 큐가 비어버릴 때 까지 3번 반복하며 꺼낸 노드들 줄세우기 (이게 위상 정렬 결과값) 백준 문제 : 2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A.. 미가공 필기(알고리즘) 2022. 2. 23.