위상정렬4 [알고리즘] 택시 (백준 1649번) 1649번: 택시 첫 번째 줄에 교차로의 개수인 N(1 2020. 11. 3. [알고리즘] ACM Craft (백준 1005번) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 그래프 상으로 본인보다 앞서 있는 건물들이 모두 지어져야 해당 건물을 지을 수 있다는 설정을 보면 알 수 있듯이 위상 정렬을 쓰는 문제다. 다만 건물 건설 시간이 각각 다르다보니 기교를 가해야한다. 결론적으론 '위상정렬 + DP' 문제다. Solution 1. topologicalSort 함수 static int topologicalSort(int N, int W, int[] complete_time, ArrayList graph, int inEdge[].. 2020. 10. 5. [알고리즘] 줄 세우기 (백준 2252번) 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net N, M의 크기만 봐도 알 수 있지만 그래프 완전탐색 문제이며 N은 정점, M은 간선의 수를 나타낸다. 정확히는 위상 정렬 문제다. 각 노드보다 앞서 있는 노드들이 먼저 출력되어야 하는 형태를 가진다. Solution import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStre.. 2020. 9. 28. [알고리즘] 위상 정렬 (Topological Sorting) 위상 정렬 (Topological Sorting) 사이클이 없는 유향 그래프의 모든 정점을 정렬하는 알고리즘 간선 (i, j) 가 존재하면 정점 i는 반드시 정점 j보다 앞에 위치해야한다. → 사이클이 있으면 이 성질을 만족할 수 없다. 시간 복잡도 : O(V+E) 알고리즘 각 노드마다의 진입 간선을 보관하는 배열 in_edge 생성 맨 처음, 진입 간선이 없는 노드들을 queue에 추가 queue가 빌 때까지 반복문 실행 현재 노드 now 출력 now에 연결된 진출 노드들 탐색 진출 노드 next의 진입 간선 줄이기 next의 진입 간선이 0이면 next 앞에 있는 노드들이 모두 출력되었다는 의미이므로 next를 queue에 추가 import java.util.*; public class Main { .. 2020. 9. 17. 이전 1 다음
