[BOJ] 백준 2150번 : Strongly Connected Component (JAVA)

문제

방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.

 

방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.

 

 

 

 

예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다.

 

 

입력

첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다.

 

다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다.

 

이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A → B가 된다.

 

정점은 1부터 V까지 번호가 매겨져 있다.

 

 

출력

첫째 줄에 SCC의 개수 K를 출력한다. 다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다.

 

각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.

 

 

풀이

강한 연결 요소 즉, SCC 입문 문제였습니다.

 

 

SCC를 푸는 알고리즘은 크게 타잔 알고리즘과 코사라주 알고리즘이 있습니다.

 

저는 그 중에서 코사라주 알고리즘을 활용하여 풀이하겠습니다.

 

자세한 SCC 및 코사라주 알고리즘에 관한 설명은 이곳을 참고해 주시고, 저는 java로 코사라주 알고리즘을 구현하는 것에 초점을 맞추겠습니다.

 

 

먼저, 코사라주 알고리즘을 구현하기 위해서 필요한 준비물을 알아야 합니다.

 

방향 그래프, 역방향 그래프, 스택으로 3가지가 필요합니다.

 

방향 그래프는 원래 입력값으로 만든 그래프를 의미하고, 역방향 그래프는 각각의 그래프에 대해서 방향을 역으로 바꾼 그래프를 말합니다. 가령, A -> B -> C라는 그래프가 있다면, 역방향 그래프는 C -> B -> A가 되는 것입니다.

 

처음에 방향 그래프에 대하여 DFS를 수행하면서 종료되는 점부터 스택에 push 합니다.

 

당연하게도 스택의 top은 처음 DFS를 수행한 시작점이 될 것입니다.

 

그리고 스택에서 하나씩 pop 하면서 역방향 그래프의 DFS를 수행합니다. 여기서 pop한 요소와 만나는 정점들은 모두 SCC를 형성하는 그룹이 됩니다.

 

참고로, 역방향 그래프에 대해 DFS를 수행할 때, 결과값을 담아야 합니다. 가령, (1, 3, 4)가 하나의 SCC를 이룬다면 res = {(1, 3, 4), (), () ,...} 와 같이 결과값을 담아야 합니다.

 

마지막으로, 출력을 올바르게 해야 합니다.

 

예제를 보면 알 수 있듯이, 처음에 SCC 그룹의 개수를 출력하고, 이후에는 SCC 그룹의 각 요소들을 나열합니다.

 

이 때, SCC 그룹 내의 요소는 오름차순 정렬되어있어야 하며, SCC 그룹의 첫 번째 요소가 작은 순서대로 출력이 되어야 합니다.

 

그룹 내의 요소는 Collections.sort()를 사용하고, SCC 그룹의 첫 번째 요소가 작은 순서대로 출력하기 위해서는 TreeMap을 통해 key 값을 정렬하면 됩니다.

 

여기서 key는 SCC 그룹 내의 첫 번째 요소이고, value는 key가 속한 그룹의 인덱스 번호에 해당합니다.

 

정렬이 끝났으면 차례대로 출력하면 되는데, 하나의 SCC 그룹의 출력이 끝나면 마지막에 -1을 붙여주어야 합니다.

 

 

자세한 내용은 아래 코드와 주석문을 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.