SCC 문제들! 백준) 2150, 4013, 4196

다음에 길게 길게 설명하기로 하고,

문제 풀면서 느낌 감상만 먼저 옮기려고 합니당.

학교 수업시간에 배운 두번의 DFS로 SCC들을 구하는 방법과,

한 번의 dfs로 SCC들을 구하는 방법을 비교해 봤는데, 확실히 후자의 방법이 두 배 정도 더 빨랐다.

두 번의 dfs는 간단해서 짜는데 빠르게 짤 수 있는 반면, 한 번의 dfs는 이해한지 얼마 안돼서 그런가 코드가 길긴하다.

간단히 설명하면,

전자의 방법은 먼저 dfs를 돌긴하는데 finish되는 순으로 stack에 push 해두었다가,

pop하면서 역간선 그래프에 대해 dfs를 다시 돌면서 scc로 묶는 방법이다. (a->b로 갈 수 있으면, b->a로도 갈 수 있어야 한다.)

후자의 방법은 dfs 트리를 활용하는데, 방문하는 순서대로 노드들에게 번호를 매기면서 stack에 push하고, 지금의 dfs가 어떤 노드로부터 

시작되었는지를 활용하여 scc로 묶는 방법이다. 후자는 확실히 코드를 봐야 이해가 빠르다.

Strongly Connected Component

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

1. 2150 은 기본 문제로 scc들을 구하는 문제였다.

도미노

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

2. 4196은 scc를 구한 다음에 더 풀어야 되는 문제였다.

scc내에선 하나만 무너지면 다른 노드들도 다 넘어진다. 따라서 그래프를 scc들 끼리의 그래프로 재편집한다음에,

scc들의 indegree를 계산하고, indegree가 0인 scc들의 갯수를 세면 풀 수 있다.

ATM

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

3. 4013은 scc를 구하고 indegree를 구하고 더 풀어야 되는 문제였다.

scc를 구할 때 각 scc들의 value 합을 구해놓고 scc들 끼리의 그래프로 재편집해야 한다.

이후 indegree를 계산한 다음에, 위상정렬로 출발점이 속한 scc에서 레스토랑이 있는 scc까지의 최대 value 합을 각각 구하면 된다.