위상정렬2

• 

  [c++] 위상정렬 백준-게임개발 1. 문제 2. 입 출력 1. 생각해볼 것 처음엔 위상정렬을 한 후 누적합을 구하는 문제인 줄 알았다.. 하지만 하나 놓치고 있었던 것이 있었다. 건물이 동시 다발적으로 건설 될 수 있었다는 것이다. 즉, 4 1 4 3 2 -1 2 4 -1 1 4 -1 1 -1 위와 같은 입력이 있을 때 누적합으로 구한다면 1번 건물은 4 3 2가 선행되어야 하므로 dist[4]+dist[3]+dist[2]+dist[1] = 5가 되어야한다. 2번 건물은 4가 선행되어야 하므로 dist[2] + dist[4] = 3 3번 건물은 4가 선행되어야하므로 dist[3] + dist[4] = 2 4번 건물은 선행되어야하는 건물이 없으므로 그대로 dist[1] = 1이 된다. 그러나 답은 4 3 2 1이 된다. 왜일까? 위의 그.. c++/알고리즘 2023. 1. 27.

• 

  [c++] 알고리즘 그래프 - 위상 정렬 - 백준 - 줄 세우기 2252 위상 정렬이란? 위상 정렬이란 어떤 집합에서 원소들의 우선 순위 정렬이라고 할 수 있겠다. 또한 위상정렬은 비순환 방향 그래프 즉 (DAG : Directed Acyclic Graph)에서 가능하다. 즉 그래프를 이루는 노드들 간의 순환이 존재하지 않게 방향이 존재할 때 가능한 정렬이다. DAG 위와 같은 DAG그래프를 선형적 그래프로 변경하는 것을 위상정렬이라고 한다. 위상정렬은 말 그대로 위상을 정렬한다는 뜻으로 이 정렬에는 각 노드들의 우선 순위가 중요하다. 또한 우선 순위만을 고려하기 때문에 최종 결과 값이 여러 개가 될 수 있다. 즉 위의 비선형 그래프는 다음과 같은 뜻을 내포한다. 1보다는 0이 선행되어야한다. 1보다는 4가 선행되어야한다. 2보다는 1이 선행되어야한다. 2보다는 4가 선행되어.. c++/알고리즘 2023. 1. 25.