BOJ-백준 2150번 SCC C++

BOJ-백준 2150번 SCC C++ 문제 풀이 입니다.

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

2150번: Strongly Connected Component

 

 

 

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 10001
using namespace std;

int id, d[MAX];
bool finished[MAX];
vector<int> graph[MAX];
vector<vector<int>> SCC;
stack<int> s;
int v,e;
int dfs(int x){
  d[x] = ++id; //노드마다 고유한 번호 할당
  s.push(x);
  int parent = d[x]; 
  //처음 부모값은 자기 고유번호 초기화
  for(int i=0; i <graph[x].size(); i++){
    int y = graph[x][i];
    if(d[y] == 0) parent = min(parent, dfs(y));
    else if(!finished[y]) parent = min(parent, d[y]);  
  }
  if(parent==d[x]){
    vector<int> scc;
    while(1){
      int t = s.top();
      s.pop();
      scc.push_back(t);
      finished[t] =true;
      if(t == x) break;
    }
    sort(scc.begin(), scc.end());
    SCC.push_back(scc);
  }
  return parent;
}

bool compare(vector<int> a, vector<int> b){
  return a[0] < b[0];
}

int main() {
  cin >> v >> e;
  for(int i =0; i < e;  i++){
    int a,b;
    scanf("%d %d",&a, &b);
    graph[a].push_back(b);
  }
  for(int i= 1; i<=v; i++){
    if(d[i]==0) dfs(i);
  }
  cout<< SCC.size() << endl;
  sort(SCC.begin(), SCC.end(), compare);
  for(int i=0; i<SCC.size(); i++){
    for(int j=0; j <SCC[i].size(); j++){
      printf("%d ", SCC[i][j]);
    }
    printf("-1\n");
  }
}

 

📌 해설

그래프 정보를 받아 SCC(Strongly Conneted Component)를 구하는 문제입니다. SCC는 서로 강하게 결합된 정점 집합을 의미합니다. 같은 SCC에 속하는 두 정점은 서로 도달이 가능합니다. 그래서 양방향 그래프에서는 무의미합니다. DFS를 사용하는 타잔 알고리즘으로 문제를 풀어보았습니다. 

 

🚩주의

vector<vector<int>> SCC 로 SCC를 선언해주었고 sort를 할때 영향이 있다고 생각되서 따로 compare함수를 만들어서 sort해주었는데 compare 없어도 알아서 정렬됩니다.ㅠ 

다 삽질 몇번 하면서 실력이 좋아진다 생각합니다..ㅎ

 

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 10001
using namespace std;

int id, d[MAX];
bool finished[MAX];
vector<int> graph[MAX];
vector<vector<int>> SCC;
stack<int> s;
int v,e;

1. 필요한 변수를 모두 선언해줍니다. 

1-1. d에는 부모값을 저장합니다. id는 부모값 초기화에 필요한 변수입니다. 

1-2. finished에는 dfs를 수행하며 dfs가 끝났는지 여부를 판별하는 변수입니다. 

1-3. graph에 모든 노드에 연결 정보를 담습니다. 

1-4. 각 SCC에 해당되는 노드들을 구별하여 담기 위해 vector<vector<int>> 로 선언합니다.

1-5. 스택과, 정점 수 v, 간선 수 e를 선언합니다. 

 

int main() {
  cin >> v >> e;
  for(int i =0; i < e;  i++){
    int a,b;
    scanf("%d %d",&a, &b);
    graph[a].push_back(b);
  }
  for(int i= 1; i<=v; i++){
    if(d[i]==0) dfs(i);
  }
  cout<< SCC.size() << endl;
  sort(SCC.begin(), SCC.end(), compare);
  for(int i=0; i<SCC.size(); i++){
    for(int j=0; j <SCC[i].size(); j++){
      printf("%d ", SCC[i][j]);
    }
    printf("-1\n");
  }
}

2. main

2-1. 정점 수 v, 간선 수 e, 그래프 연결 정보를 입력받습니다. 

2-2. 모든 정점에 대해 dfs를 수행합니다. 

이때, 부모노드가 한 번도 초기화 되지 않은 (0으로 초기화된) 노드 i에만 dfs를 수행하도록 합니다. 

2-3. SCC 를 정렬(sort)하고 결과를 출력합니다. 

 

int dfs(int x){
  d[x] = ++id; //노드마다 고유한 번호 할당
  s.push(x);
  int parent = d[x]; 
  //처음 부모값은 자기 고유번호 초기화
  for(int i=0; i <graph[x].size(); i++){
    int y = graph[x][i];
    if(d[y] == 0) parent = min(parent, dfs(y));
    else if(!finished[y]) parent = min(parent, d[y]);  
  }
  if(parent==d[x]){
    vector<int> scc;
    while(1){
      int t = s.top();
      s.pop();
      scc.push_back(t);
      finished[t] =true;
      if(t == x) break;
    }
    sort(scc.begin(), scc.end());
    SCC.push_back(scc);
  }
  return parent;
}

3. dfs를 수행합니다.

3-1. dfs 를 수행할 노드 x에 부모노드를 초기화 합니다. (d[x] = ++id) 

모든 노드에 한 번씩만 d[x]가 초기화 되기 때문에 id 를 증가시키며 부모값이 자기 자신이 되도록 합니다. 

3-2. 스택에 자기 자신의 값을 넣습니다. 

3-3. d[x] (부모값)을 parent에 저장합니다. 

3-4. x에 연결된 노드를 탐색할 수 있는 for문을 작성합니다. 

    3-4.(1) 만약, y가 단 한번도 방문한 적 없는 (부모노드가 0으로 초기화된) 노드라면 x의 부모값과 y에 연결된 부모값중 더 작은 값을 parent에 저장합니다. 

    3-4.(2) 만약, y가 한 번이라도 방문 된 적 있는 노드인데, 아직 dfs가 종료되지 않은 노드라면, x의 부모값과, y의 부모값 중 더 작은 값을 parent에 저장합니다. 

3-5. x에 연결된 모든 y에 대한 탐색이 끝났다면, x의 갱신된 부모값이 갱신 전 부모값(자기 자신)과 동일한지 비교합니다. 

3-6. 동일하다면 SCC를 형성합니다. 

    3-6.(1) scc를 형성할 노드들을 담은 vector를 한개 선언합니다. 

    3-6.(2) 스택을 top에서 하나씩 빼서 scc 벡터에 담습니다. 뺀 원소는 finished에서 종료 여부를 true로 갱신합니다. 

    3-6.(3) 스택에서 모든 원소를 뺐다면 반복문을 종료 하고 scc벡터를 정렬합니다. 

    3-6.(4) 정렬된 scc벡터를 SCC에 담습니다. 

3-7. dfs는 parent를 반환하며 종료합니다.

 

 

 

::