[BOJ] 백준 2252. 줄 세우기

▶문제설명

[BOJ] 백준 2252. 줄 세우기

https://www.acmicpc.net/problem/2252

▶Hint

---

위상 정렬(Topological sort) 문제이다.

위상 정렬은 DAG(Directed Acyclic Graph : 방향성 비 사이클 그래프)에서 쓸 수 있는 알고리즘이다.

학생 N명을 줄 세우려 하는데, 일부 학생들의 키를 비교하여 누가 누구 앞에 있는지에 대한 정보를 입력으로 주고, 그에 맞추어 줄 세운 결과를 출력해야한다.

위상 정렬은 여러 개의 답이 나올 수 있고, 주어진 출력 결과와 다르더라도 위상 정렬이 제대로 되었다면 정답으로 인정된다.

DFS를 이용한 방법과 각 정정의 Indegree 값을 이용한 방법이 있는데, Indegree 값을 이용해 풀어보았다.

정점이 3개이고

1 3

2 3 

이라는 입력이 주어졌을 때, 이를 방향 그래프로 나타내면

1 → 3

      ↑

      2

이런 모양이 된다.

입력을 받으면서 각 정점에 들어오는 간선의 개수를 카운트 한다.

그러면 모든 정점을 확인하여 들어오는 간선의 개수가 0인 정점을 찾을 수 있다.

위상 정렬은 들어오는 간선의 개수가 0인 정점에서부터 시작된다.

1. queue 자료구조를 이용해 들어오는 간선의 개수가 0인 정점들을 push한다.

2. 정점들을 하나씩 pop하면서 출력하고, 해당 정점과 연결된 정점들의 Indegree 값을 1 감소시킨다.

Indegree 값이 감소하여 0이 된 경우, 해당 정점을 큐에 push한다.

3. 2의 과정을 queue에 아무 것도 들어있지 않을 때까지 반복한다.

예시로 주어진 입력으로 위와 같은 알고리즘을 수행하면 1 2 3 혹은 2 1 3 이라는 결과를 얻을 수 있다.

▶Solution