[Baekjoon - 22443] Minus One

난이도: Gold II

 

태그

• Breadth-First Search
• Combinatorics
• Meat In the Middle (알고 있을 필요는 없지만, 뭔가 그런 느낌이 있다.)

 

풀이

1. 원래의 최단 경로를 알고 있을 때, 간선을 하나 추가한 뒤의 최단 경로는?

원래의 최단 경로를 \( [s = v_0, v_1, \ldots, v_k = t] \)라고 하고, 추가된 간선을 \( {x, y} \)라고 합시다.

그럼, 새로운 그래프의 최단 경로는 원래의 최단경로이거나, \( [s, \ldots, x, y, \ldots, t] \)라는 새로운 경로가 됩니다.

 

\( d(v, w) \)를 \( v \)에서 \( w \)로 가는 최단 경로의 길이라고 하면,

우리가 찾은 경로의 길이는 \( d(s, x) + 1 + d(y, t) \)가 됩니다.

 

2. 간선을 추가한 뒤의 최단 경로가 이전의 최단 경로 - 1이 되려면?

\( d(s, x) + 1 + d(y, t) = k - 1 \)이므로, \( d(s, x) + d(y, t) = k - 2 \)여야 합니다.

 

3. \( d(s, x) \)를 고정할 때, 가능한 경우는?

\( d(s, x) \)가 고정되면, \( d(y, t) \) 역시 고정됩니다.

이 때의 경우의 수는 \( x \)를 고르는 경우의 수 × \( y \)를 고르는 경우의 수가 되고,

\( x \)를 고르는 경우의 수는 \( d(s, x) \)를 만족하는 \( x \)의 개수가 됩니다.

\( y \) 역시 비슷하게, \( d(y, t) \)를 만족하는 \( y  \)의 개수가 되겠죠.

 

4. 코드

vector<int> adj[100020];
 
int dis[2][100020];
int num[2][100020];
void bfs(int idx, int st){
    memset(dis[idx], -1, sizeof(dis[idx])); dis[idx][st] = 0; num[idx][0] += 1;
    queue<int> q; q.push(st);
    while (!q.empty()){
        int now = q.front(); q.pop();
        for (int nxt : adj[now]){
            if (dis[idx][nxt] != -1){ continue; }
            dis[idx][nxt] = dis[idx][now]+1; num[idx][ dis[idx][nxt] ] += 1;
            q.push(nxt);
        }
    }
}
 
void Main(){
    int n, m, st, ed; cin >> n >> m >> st >> ed;
    while (m--){
        int v, w; cin >> v >> w;
        adj[v].push_back(w); adj[w].push_back(v);
    }
    bfs(0, st); bfs(1, ed);
    int d = dis[0][ed];
    ll ans = 0;
    //for (int i = 0; i <= n; i++){ cout << "NUM " << i << "   " << num[0][i] << ' ' << num[1][i] << endl; }
    for (int i = 0; i <= d-2; i++){
        ans += 1LL*num[0][i]*num[1][d-2 - i];
    }
    cout << ans;
}