[백준] No.3997 - 축구 전술 (C++, SCC, 타잔 알고리즘)

문제

 

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

3977번: 축구 전술

 

 

풀이

 

solved.ac 난이도: Platium 4

 

 

강한 결합 컴포넌트(SCC,Strongly Connected Component)로 해결해야 하는 문제.

 

SCC를 모른다면 굉장히 풀기 힘드니 먼저 공부하고 오자.

방향 그래프에서 두 정점이 서로 이동 가능한 경로가 있는 경우 해당 정점들은 같은 강한 결합 컴포넌트에 속한다.

 

예를 들어 아래의 방향 그래프에서 같은 SCC끼리를 사각형으로 묶으면 다음과 같이 나타난다.

 

위와 같이 SCC로 표현을 하고 SCC를 각각 하나의 정점이라고 생각한다면 사이클이 존재하지 않는 그래프, DAG(Directed Acycle Graph) 로 나타낼 수 있다.

 

그래프의 SCC들을 확인하는 알고리즘으로 코사라주와 타잔 알고리즘이 있다.

본인의 풀이에서는 타잔 알고리즘으로 이번 문제를 해결하였다.

 

 

 

이제 문제를 확인해보자.

 

시작 구역이란 모든 구역에 도달 할 수 있는 구역을 말한다.

그래프의 용어로 바꾸어 표현하면 방향 그래프에서 모든 정점에 도달할 수 있는 시작 정점들 찾으라는 것이다.

 

만약 시작 정점들끼리 사이클, 즉 SCC를 이룬다면 해당 SCC의 어느 정점에서 출발하여도 SCC내의 모든 정점으로의 경로가 있기 때문에 그래프의 모든 정점으로 도달이 가능하다.

이제 시작 정점들끼리 이루는 SCC를 시작 SCC라고 표현하자.

 

위에서 설명했듯이 각각의 SCC를 노드로 생각하면 그래프는 DAG로 나타내진다.

DAG에서 모든 정점에 도달 가능한 정점이 있는 경우는 바로 진입 차수(노드로 들어오는 간선의 수, indegree)가 0인 정점이 단 1개만 존재하는 경우이다.

 

위와 같은 그래프에서는 진입 차수가 0인 SCC가 두 개 존재한다.

이 경우 서로의 SCC로는 접근이 불가능하므로 두 SCC의 정점들은 모든 정점에는 도달할 수 없다.

 

따라서 indegree가 0인 SCC의 개수를 알아내는 코드를 구현해보자.

일단 SCC들의 indegree를 구하자.

 

타잔 알고리즘에서는 이미 방문한 정점이 SCC에 속해 있는지를 확인했다.

만약 속해있지 않다면 해당 정점과 같은 SCC에 속하게 되었다.

 

이번에는 이미 방문한 정점이 SCC에 속해있는 경우를 생각해보자.

이미 SCC를 이룬 정점에 접근했다는 것은 해당 SCC로의 진입이 있다는 것이다.

따라서 SCC의 indegree를 증가시켜주자.

 

다음으로는 스택을 이용하여 SCC를 그룹 지어 주는 경우이다.

타잔 알고리즘에서는 자신의 위에 쌓이는 정점들은 모두 자신보단 하위 노드임을 이용하여 SCC를 그룹화한다.

만약 스택에서 같은 SCC를 모두 꺼내 주었는데도 스택이 비지 않았다면 다른 정점으로 해당 SCC가 접근이 가능하다는 것이다.

 

 

 

위와 같은 그래프에서 타잔 알고리즘을 진행 시, 3,2,1이 순서대로 스택에서 pop 되어 SCC를 이룬다.

하지만 스택에는 1로 접근 가능한 정점 0이 남아있다.

 

따라서 스택이 비지 않았다면 새로 구성한 SCC의 indegree를 +1해 주자.

 

이러한 방식으로 변경한 타잔 알고리즘은 다음과 같다.

 

 

const int MAXN = 100001;
 
int area_num, movement_num;
vector<vector<int>> adj;
vector<int> visited_order;
stack<int> st;
vector<vector<int>> scc_set;
int scc_number[MAXN];
int indegree[MAXN];
int order, scc_cnt;
 
int FindSCC(int now_area){
  int next_area;
  int min_order = visited_order[now_area] = order++;
  st.push(now_area);
 
  for(int i=0; i < adj[now_area].size() ; ++i){
    next_area = adj[now_area][i];
    if(visited_order[next_area] == -1)
      min_order = min(min_order, FindSCC(next_area));
    else if(scc_number[next_area] == -1)
      min_order = min(min_order, visited_order[next_area]);
    else
      indegree[scc_number[next_area]]++;  //이미 scc를 이룬 노드에 접근시 해당 scc로의 진입 차수가 증가
  }
 
  if(min_order == visited_order[now_area]){
    int temp;
    vector<int> new_scc;
 
    while(1){
      temp = st.top();
      st.pop();
      scc_number[temp] = scc_cnt;
      new_scc.push_back(temp);
      
      if(temp == now_area)
        break;
    }
 
    if(!st.empty()) //stack이 비지 않았다면 상위 노드에서 새로 구성된 SCC로의 진입이 있었다는 뜻
      indegree[scc_cnt]++;
 
    scc_cnt++;
    scc_set.push_back(new_scc);
  }
 
  return min_order;
}

 

 

 

코드