위상정렬4 [알고리즘] Directed Graph에서 사이클 찾기 방향이 있는 그래프에서 싸이클을 찾는 방법을 알아보자. Using BFS Kahn 알고리즘을 사용한다. www.geeksforgeeks.org/detect-cycle-in-a-directed-graph-using-bfs/ Detect Cycle in a Directed Graph using BFS - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.. 2023. 4. 15. [백준 1948] 임계경로 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 위상정렬 + 역추적 문제이다. 문제이해가 어려웠으나 요약하면 1. 시작점->목적지까지 도달하는데 가장 오래 걸리는 시간 구하기 2. 1만큼의 시간이 소요되는 경로에 속한 도로들의 수 구하기 이다. 1분도 쉬지 않는다는 의미가 2라는 걸 이해하지 못했다... 1을 푸는 것은 위상정렬 + dp를 결합하면 어렵지 않게 해결할 수 있으나 문제는 2였다. 2에 대해 set으로 풀.. 2021. 6. 19. [백준 9466] 텀 프로젝트 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net directed graph에서 cycle detection 응용문제이다. 사이클에 해당하지 않는 노드를 찾는 문제로 dfs를 사용하거나 indegree + 위상정렬을 사용한다. 1. dfs를 사용할 때 사이클이 있는지 확인할 때 지나간지 여부를 체크하는 배열 path와 확인이 끝났다는 표식인 done 배열 두 가지를 사용한다. 1부터 n까지 done이 아니라면 dfs에 들어가는데 dfs에 들어가서 방문 체크path를.. 2020. 12. 3. [leetcode 210] Course Schedule II There are a total of n courses you have to take labelled from 0 to n - 1. Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai. Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses. If there are many valid answe.. 2020. 11. 16. 이전 1 다음
