Henu
개발냥발
Henu
전체 방문자
오늘
어제
  • 분류 전체보기 (411)
    • DevOps (52)
      • Kubernetes (19)
      • Docker (14)
      • AWS (3)
      • Nginx (4)
      • Linux (4)
      • ArgoCD (1)
      • CN (2)
      • NATS (0)
      • Git (5)
    • Back-End (30)
      • Django (18)
      • Spring (5)
      • JPA (1)
      • MSA (5)
    • CS (87)
      • SystemSoftware (20)
      • OS (25)
      • Computer Architecture (16)
      • Network (23)
      • Database (2)
    • Lang (21)
      • Java (9)
      • Python (4)
      • C# (8)
    • Life (12)
    • 블록체인 (2)
    • Algorithm (204)
      • BOJ (160)
      • 프로그래머스 (19)
      • LeetCode (4)
      • SWEA (1)
      • 알고리즘 문제 해결 전략 (8)
      • DS, algorithms (7)
      • Checkio (5)
    • IT (2)

블로그 메뉴

  • GitHub
  • 글쓰기
  • 관리자

공지사항

  • Free!

인기 글

태그

  • DFS
  • Kubernetes
  • 프로그래머스
  • 백트래킹
  • boj
  • Network
  • 다이나믹 프로그래밍
  • BFS
  • docker
  • django

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Henu

개발냥발

[백준 2150] Strongly Connected Component C++
Algorithm/BOJ

[백준 2150] Strongly Connected Component C++

2021. 6. 10. 17:01
 

2150번: Strongly Connected Component

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

www.acmicpc.net

강한 연결 요소

ㅈㅎㄱ 교수님의 알고리즘 수업에서 강한 연결 요소 문제를 해결하기 위한 코사라주 알고리즘을 배우고 이를 적용하는 문제를 풀어보았다.


1. 문제 해결 아이디어

Graph

위와 같은 그래프를 Graph라고 하자

 

  1. Graph에서 임의의 시작 노드를 잡아서 DFS(시작)를 한다.
    • Graph가 서로 분리된 경우도 생각해야한다.(모든 정점에 대해서 DFS하기)
  2. DFS를 하면서 각 정점의 finish time을 저장한다.
  3. Graph에서 모든 간선의 방향을 반대로 바꾼 역방향 그래프 rev_Graph를 만든다.
  4. finish time이 큰 정점부터, 즉 늦게 끝난 정점부터 rev_Graph에서 DFS를 한다. 이때 생기는 DFS트리들이 각각 하나의 SCC가 된다.

rev_Graph

1번 정점이 가장 늦게 끝났기 때문에 1번부터 rev_Graph에서 DFS를 한다.

  • 4번 정점에서 DFS가 종료된다.

 

아직 방문하지 않은 3, 5, 6번 정점 중에 5번 정점이 가장 늦게 끝났기 때문에 5번부터 DFS를 한다.

  • 6번 정점을 방문하고 종료된다.

마지막으로 남은 3번에서 DFS를 한다.

위 그림과 같은 SCC를 얻을 수 있게 된다.


2. 코드

<+21> : 입력과 동시에 모든 간선의 방향을 반대로 바꾼 rev_Graph도 같이 만든다.

 

<+25> ~ <+39> : Graph에서 dfs를 하면서 가장 먼저 끝난 순서대로 rev_search_seq에 차례대로 push한다. (stack의 역할)

<+41> ~ <+53> :  늦게 끝난 정점부터 rev_Graph를 DFS하면서 DFS 트리를 구한다.

 

<+56> ~ <+59> : 아직 방문하지 않은 모든 정점에 대해서 DFS를 한다.

 

<+61> ~ <+68> : 가장 늦게 끝난 정점(stack의 top)부터 dfs를 해서 DFS 트리를 구하고, 구한 트리를 SCC에 push 한다.

 

<+76> : SCC의 개수를 출력하는걸 깜박해서 30분이나 날렸다..

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
 
//#define pii pair<int, int>
using namespace std;
 
int V, E, dtime = 1;
vector<int> Graph[10001];
vector<int> rev_Graph[10001];
vector< vector<int> > SCC;
//pii df_time[10001];
vector<int> rev_search_seq;
 
bool visited[10001], rev_visited[10001];
 
void input(){
    int a, b;
    cin >> V >> E;
    for(int i = 0; i < E; i++){
        cin >> a >> b;
        Graph[a].push_back(b);
        rev_Graph[b].push_back(a);
    }
}
 
void dfs(int now){
    
    visited[now] = true;
//    df_time[now].first = dtime++;
    
    for(int i = 0; i < Graph[now].size(); i++){
        int next = Graph[now][i];
        if(visited[next]) continue;
        
        dfs(next);
        
    }
//    df_time[now].second = dtime++;
    rev_search_seq.push_back(now);
}
 
void rev_dfs(int now, vector<int> &temp){
    
    rev_visited[now] = true;
    temp.push_back(now);
    
    for(int i = 0; i < rev_Graph[now].size(); i++){
        int next = rev_Graph[now][i];
        if(rev_visited[next]) continue;
        
        rev_dfs(next, temp);
    }
    
}
 
void solve(){
    for(int i = 1; i <= V; i++){
        if(visited[i]) continue;
        dfs(i);
    }
    
    vector<int> temp;
    for(int i = rev_search_seq.size()-1; i >= 0; i--){
        int now = rev_search_seq[i];
        if(rev_visited[now]) continue;
        rev_dfs(now, temp);
        SCC.push_back(temp);
        temp.clear();
    }
    
    for(auto &w : SCC){
        sort(w.begin(), w.end());
    }
    sort(SCC.begin(), SCC.end());
    
    
    cout << SCC.size() << "\n";
    
    for(auto &w : SCC){
        for(auto &k : w){
            cout << k << " ";
        }
        cout << "-1\n";
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    input();
    solve();
    
    return 0;
}
 
Colored by Color Scripter
cs

코사라주 알고리즘으로 풀었다.

 

타잔 알고리즘이 구현은 더 어렵지만 확장성이 더 좋다고 하니까

다른 문제는 타잔 알고리즘을 배운 뒤에 그걸로 풀어보겠다.

'Algorithm > BOJ' 카테고리의 다른 글

[백준 1708] 볼록 껍질 C++  (0) 2021.06.13
[백준 17387] 선분 교차 2 C++  (1) 2021.06.11
[백준 1600] 말이 되고픈 원숭이 C++  (0) 2021.06.09
[백준 8980] 택배 C++  (0) 2021.06.09
[백준 1167] 트리의 지름 C++  (0) 2021.06.07
    'Algorithm/BOJ' 카테고리의 다른 글
    • [백준 1708] 볼록 껍질 C++
    • [백준 17387] 선분 교차 2 C++
    • [백준 1600] 말이 되고픈 원숭이 C++
    • [백준 8980] 택배 C++

    티스토리툴바