https://www.acmicpc.net/problem/2152
문제조건
- 총 M(1 ≤ M ≤ 100,000)개의 비행로가 존재
- 각각의 비행로는 한 방향으로의 서비스만을 제공
- S(1 ≤ S ≤ N)번 도시에서 시작해서 T(1 ≤ T ≤ N)번 도시에서 여행을 끝냄
- 최대로 방문할 수 있는 도시의 개수
- 각각의 도시는 여행 중에 몇 번이든 방문할 수 있으며, 같은 항공로를 여러 번 이용할 수도 있다.
접근방법
문제를 읽고 나서 든 생각은 띠용(?) 이게 뭐야,,, 였다,,
문제 조건중 몇 번이든 같은 도시를 방문할 수 있다는 점을 이해하기가 어려웠다.
그리고 같은 항공로를 여러 번 이용한다는 말에서 조금 감이왔다. "이거 순환이 될수 있으니까 뭔가 묶어볼수 있지않을까?"
우연치 않게 학교 강의에서 들었던 SCC(Strongly Connected Component)에 대해서 떠올릴 수 있었다.
SCC : 강 결합 컴포넌트
개념 : 그래프에서 노드 간의 연결 관계가 주어질 때, 정점들의 최대 부분 집합으로, 부분 집합에 들어있는 서로 다른 노드 u와 노드 v에 대하여, u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 뜻한다. 즉, 그래프상에서 이해하자면 cycle이 있는 경우에 해당한다.
코사라주 알고리즘과, 타잔의 알고리즘이 있는데 타잔의 알고리즘은 코드는 간결하지만 머리속으로 이해가 되지않아서 코사라주 알고리즘으로 익혔던 기억이난다.
그래서 코사라주에 대해서 설명하고자 한다.
코사라주 알고리즘
먼저 필요한 것들이 있다.
- 순방향 그래프
- 역방향 그래프
- 스택
구현 방식은 DFS로 진행한다. 코사라주알고리즘은 DFS를 두번 진행해서 구현한다.
- 순방향그래프에서 임의의 점부터 시작해서 DFS로 방문한다. (이때, 한 노드에서 시작해서 DFS를 마치면 이것이 하나의 그룹이 된다.)
- 탐색이 끝난 순서(함수가 종료된 순서)로 스택에 PUSH 한다.
- 스택의 top 에서부터 pop을 하여 순서대로 역방향 그래프에서부터 DFS를 수행한다.(스택이 비어있을때 까지)
- 이미 방문했던 점이 탐색되면 POP한다.
- 탐색되는 정점들을 SCC로 묶는다.
이문제만의 특성은 같은 도시를 여러 번 방문하는 경우는 한 번만 생각하기로 한다. 라고 했으므로, set자료구조를 이용했다.
- 핵심 : 각 SCC를 하나의 노드라고 생각하고 BFS를 진행해서 최댓값을구한다!
소스코드
#include <iostream>
#include <vector>
#include <cstring>
#include <set>
#include <stack>
#include <queue>
#define MAX 10001
using namespace std;
int N, M, S, T;
int idx, cnt[MAX];
vector<int> path[MAX], rev[MAX];
stack<int> stk;
set<int> edge[MAX];
int visited[MAX], group[MAX];
int res;
//순방향 그래프 탐색
void forward(int num) {
if (visited[num]) return;
visited[num] = 1;
for (int i = 0; i < path[num].size(); i++) forward(path[num][i]);
stk.push(num);
}
int back(int num) {
if (visited[num]) return 0;
visited[num] = 1;
int tmp = 1;
for (int i = 0; i < rev[num].size(); i++) tmp += back(rev[num][i]);
group[num] = idx;
return tmp;
}
void bfs(int start, int end) {
queue<pair<int, int> > q;
q.push({ start, cnt[start] });
while (!q.empty()) {
int s = q.front().first;
int city = q.front().second;
q.pop();
if (s == end) res = max(res, city);
else {
for (auto i : edge[s]) {
if (visited[i] < city + cnt[i]) {
visited[i] = city + cnt[i];
q.push({ i, visited[i] });
}
}
}
}
}
int main(){
cin >> N >> M >> S >> T;
int a, b;
for (int i = 0; i < M; i++) {
cin >> a >> b;
path[a].push_back(b);
rev[b].push_back(a);
}
for (int i = 1; i <= N; i++) {
if (!visited[i]) forward(i);
}
memset(visited, 0, sizeof(visited));
//SCC 그룹 번호 부여
while (!stk.empty()) {
if (!visited[stk.top()]) {
idx++;
cnt[idx] = back(stk.top());
}
stk.pop();
}
//각 SCC그룹간의 엣지
for (int i = 1; i <= N; i++)
for (auto a : path[i])
if (group[i] != group[a]) edge[group[i]].insert(group[a]);
memset(visited, 0, sizeof(visited));
bfs(group[S], group[T]);
cout << res;
return 0;
}
정말 오래 걸렸던 문제이고, 여러가지 알고리즘들이 결합되어 있어서 많이 틀렸다,, 드문 유형의 문제인데 또 이런 유형을 만난다면 맞출수 있다는 자신감(?)이 생겼닿ㅎㅎ