문제설명
접근방식
이번 방학부터 시작한 코드포스 스터디에서 진행한 Virtual 연습풀이 때 마주한 문제였다. 끝나고 나서 알았지만 div2를 풀어야 했는데 div1을 풀어서 B번 문제부터 이런 어마무시한 문제를 만나버리게 됐다.
사실 문제풀이에 사용되는 개념도 쉽고 해결 자체도 매우 간단하게 해결되는데 반해 아이디어를 생각해내기가 매우 어려웠던 문제라서 그렇기에 아주 좋은 문제라고 생각됐다. 우선 문제는 보이다시피 그래프 문제인데 정점 간의 path를 확인해줘야 하는 문제이다. 정점들간의 연결성을 바탕으로 그래프 정보가 주어지고 추가로 박람회가 열리는 두 정점이 고정된다. 여행을 떠나는 입장에서 어떤 루트를 짠다하더라도 제시된 두 박람회가 열리는 도시를 무조건 지나게 하는 정점의 쌍을 찾아야 한다. 박람회 정점을 기준으로 정점들을 다음과 같이 구분해서 문제를 풀어야 한다는 느낌을 받을 수 있었다.
A 뒤 출발정점들 | A | A~B 사이의 정점들 | B | B 뒤 도착정점들
이런 형식으로 정점들을 묶어줄 수 있으면 뒤 정점들간의 순서쌍 묶기만 해주면 되서 문제가 간단히 풀릴 것 같은데 저 분류 자체를 할 수 있는지와 그렇다면 어떻게 할 수 있는지를 떠올리는 것이 쉽지는 않았다. 먼저 든 생각은 물론 개념과 구현에 대한 이해가 낮아서 할 수도 없었을 것 같기는 하지만 위상정렬이었다. A와 B 정점을 중심으로 해서 위상정렬을 진행하면 정점들을 범주화 할 수 있지 않을까 하는 생각이었는데 역시 개념도 정확히 모르는 것 같아서 다시 공부해야한다는 필요성만 느꼈다.
그러고나서 아무리 그래프 예시를 그려보면서 생각을 해봤지만 전혀 아이디어를 얻을 수 없어서 빠르게 포기하고 구글링으로 넘어갔다. Codeforce 문제라서 그런지 백준 문제들보다 힌트를 얻는 것도 어려웠는데 설명을 들을 수는 없었지만 코드들을 보면서 어떤 아이디어로 접근해야하는지 알 수 있었다.
핵심개념
아이디어는 DFS로 탐색을 하되 탐색에서 Blocking을 걸어주는 것이었다. 일단 위의 정점 구분 접근 자체는 옳게 접근한 것이었고 이를 DFS를 통해서 생각보다 간단하게 구현할 수 있었다. 문제에서 연결 그래프임을 전제했기 때문에 A에서 DFS 탐색을 하게 되면 당연히 모든 정점을 탐색할 수 있는데 여기서 정점 B를 탐색하게 되면 더 이상 깊게 탐색하지 않도록 Blocking을 걸어준다. 그렇게 되면 A에서 출발해서 탐색하지 못 하는 정점들은 "B 뒤 도착정점들"이 된다. B를 거치지 않고 해당 정점에서 도착할 수 있다면 분류자체가 "A~B 사이의 정점들"이 되어버리기 때문이다. 따라서 이런 방식으로 A에서 B를 Blocking해서 DFS 탐색 한 번, B에서 A를 Blocking해서 DFS 탐색 한 번 진행해주면 각각 박람회 뒤 정점들을 구할 수 있게 되고 이를 순서쌍으로 묶는 경우의 수는 각각을 곱해주면 된다.
추가적으로 구현할 때는 다수의 테스트 케이스를 처리해야 하므로 그래프와 방문정보 여부를 저장하는 배열들을 각 테스트 케이스에 맞춰서 초기화해주는 것을 신경써줘야 한다.
C++코드
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair <ll, ll>;
vector<vector<int>> G;
vector<bool> visited;
void DFS(int cur, int key){
visited[cur] = true;
if(cur == key)
return;
for(int next : G[cur]){
if(!visited[next])
DFS(next, key);
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("inp.txt", "r", stdin);
int t;
cin >> t;
while(t--){
int n, m, a, b;
cin >> n >> m >> a >> b;
G.resize(n+1);
for(int i=0; i<=n; i++){
while(!G[i].empty())
G[i].pop_back();
}
visited.resize(n+1, false);
fill(visited.begin(), visited.end(), false);
while(m--){
int src, dst;
cin >> src >> dst;
G[src].push_back(dst);
G[dst].push_back(src);
}
ll cnt1 = 0;
DFS(a, b);
for(int i=1; i<=n; i++){
if(!visited[i])
cnt1++;
}
ll cnt2 = 0;
fill(visited.begin(), visited.end(), false);
DFS(b, a);
for(int i=1; i<=n; i++){
if(!visited[i])
cnt2++;
}
cout << (ll)cnt1 * cnt2 << '\n';
}
}