백준 2252 (2) 썸네일형 리스트형 C++ 백준 2252 (줄 세우기) 백준 2252 (줄 세우기) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 설명 이 문제는 위상정렬(DFS)를 통해 간단히 풀 수 있는 문제였다. 위상정렬에 대한 설명은 위상정렬(링크)에 자세히 설명이 되어있다. 예제입력으로 각 일에 대한 순서들이 주어지는데 각 일을 하나의 노드로 생각하고 방향성이 있는 그래프로 생각하면 된다. 예를 들어 1 2 가 입력되었다면 1번노드에서 2번노드로 가는 길이있다고.. 위상정렬 (Topological Sort) 알고리즘 위상정렬 해당 내용을 이해하기 위해선 DFS(링크)에 대한 이해가 필요하다. 위상정렬(Topological Sort)는 DFS를 사용하는 대표적인 알고리즘이다. DFS말고 indegree의 개수를 측정하는 방법도 있다. 알고리즘의 목표는 일의 순서를 정하는 것이다. 예를 들어 W1, W2, W3 (W는 할 일이다)이 있다고 가정하자. W2는 W1을 끝내야만 할 수 있고, W3은 W2를 끝내야만 할 수 있다. 그렇다면 일의 순서는 W1 → W2 → W3로 하면 될 것이다. 예시는 3개밖에 없어서 간단한 암산으로 금방 해결할 수 있지만, 주어진 정보가 많아진다면 골치가 아파진다. 이때 사용하는 알고리즘이 바로 위상정렬이다. 다음과 같은 그래프가 있다. 각 노드는 위에서 언급한 '일'이라고 생각한다. 모든 노.. 이전 1 다음
