Topological sort
-
백준 2056 작업Algorithm/BOJ 2021. 6. 3. 13:32
출처: https://www.acmicpc.net/problem/2056 분류: 위상정렬 접근방식 나보다 먼저 수행되어야 할 작업이 필요한 위상정렬에 관한 문제였습니다 :) 각 작업을 Node로 정의해서 나보다 먼저 수행되어야 할 작업들을 진입차수, inDegree 내가 끝나길 기다리고 있는 작업들을 nextTasks로 가지고 있도록 만들었습니다. 내가 수행하는 데 걸리는 시간을 workingTime 그리고 자신이 끝나는 시간 endTime을 가지고 있도록 했습니다. (우선 초기값은 workingTime이고 내가 기다리던 작업이 끝날 때마다 업데이트 시킵니다.) inDegree가 0인 작업들은 바로 시작이 가능하므로 큐에 담아서 실행시키고, 작업이 끝나면 기다리던 노드로 가서 inDegree를 줄이고 n..
-
백준 1005 ACM CraftAlgorithm/BOJ 2021. 4. 19. 15:30
출처: www.acmicpc.net/problem/1005 분류: 위상정렬 접근방식 특정 순서가 있는 방향성 비순환 그래프(DAG)로 위상정렬의 개념으로 해결할 수 있는 문제였습니다. 위상정렬 개념 다시보기 다음 건물을 짓기 위해서는 그 전의 건물이 모두 다 지어져야 하므로 해당 건물을 짓기 위해 필요한 시간을 체크하는 배열을 하나 두고 연결을 끊으면서 가장 오래 걸리는 시간으로 업데이트를 해줍니다. for adj in adjacent[run] { adjCount[adj] -= 1 if totalTime[adj] < totalTime[run] + runTime[adj] { totalTime[adj] = totalTime[run] + runTime[adj] } if adjCount[adj] == 0 { r..
-
백준 2252 줄 세우기Algorithm/BOJ 2021. 1. 27. 22:16
출처: https://www.acmicpc.net/problem/2252 분류: 위상정렬 접근방식 위상정렬로 해결할 수 있는 문제였습니다 :) 특정 순서를 지켜야 하고 방향성 있는 그래프 일 때는 위상정렬!! 을 다시 한번 기억해야겠습니다. 해결방법 큐를 구현하긴 귀찮고 removeFirst도 사용하기 싫어서 큐 인덱스를 가리키는 변수를 하나 만들어서 FIFO를 구현해봤습니다 :) protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()!..
-
위상정렬 Topological SortAlgorithm/Theory 2020. 6. 7. 13:21
목표 - 위상정렬 (Topological Sort)를 이해하고 설명할 수 있다. - 위상정렬의 조건을 알고 언제 어떻게 사용하는지 이해한다. 위상정렬? \ 특정한 순서를 가진 조건에서 사용한다. DAG(방향성 비순환 그래프) 에서만 사용할 수 있다. \ "위상" 이라는 사전적 정의에서 알 수 있듯이, 위상정렬이란 어떤 순서를 가지고 있는 경우에 사용할 수 있는 정렬 방법입니다. 게임을 하는데 어떤 스킬을 익히기 위해 반드시 먼저 배워야 하는 사전스킬이 있죠? 이런 식으로 어떤 순서를 가지고 있을 때 사용합니다. 이 말인즉 위상정렬은 방향성을 가지고 있어야 합니다. 그리고 이 의미를 잘 생각해보면 사이클이 생기면 안된다는 것을 알 수 있습니다. A -> B -> C 순서를 가지고 있어야 하는데 여기서 C ..