[수학&그래프이론] 제1회 곰곰컵 H번, 곰곰이의 심부름

<문제의 접근>

 문제에서 나오는 최단경로로 힌트를 얻을 수 있다. 일단 최단 경로를 구해야 한다. 최단 경로를 구하는 방법도 여러가지지만, 일단 벨만 포드로 구해볼 수도 있을 것 같은데, 벨만포드의 시간복잡도는 O(VE)이기 때문에 현 문제에서는 사용이 불가능할 것으로 보인다. 특별히 간선에 가중치도 없는 것으로 보았을 때 그냥 BFS로 진행해도 될 것 같다. 생각해야 할 부분은 최단 거리를 시작에서 목적지 까지 구하는 것이 아니라, 시작에서 심부름까지 그리고 심부름에서 목적지 까지 따로 구해야 한다는 것이다.

 이걸로 한고비 넘겼고, 다음은 경로가 구해지면 어떻게 순서쌍의 갯수를 구하느냐이다. 여기서 수학의 개념이 들어가는데, 처음으로 생각해야 할 점은 이 그래프는 N개의 정점과 N-1개의 간선으로 이루어진 그래프로써, 순환이 없는 유일한 경로를 가진 그래프라는 점이다. 따라서 어떠한 경로를 찾던지 유일한 경로로, 대안이 없다. 그렇다면 장점은? 경로를 일일이 알 필요는 없고, 갯수만으로도 뭔가를 구할수 있다는 점이다. 

<수학 계산>

 아래의 노트를 확인해 보자.

 <구현>

 이제 구현하는 일만 남았다. 어떻게 구현해야 할까? 기본적으로 BFS는 방문 횟수를 구해주기 위해서 pair를 이용했다. 쉽게 구현하기 위해 deque를 사용해서 while문을 돌리면 된다. 한가지 주의해야 할 점은 그래프에 간선이 없을 때를 처리해 주기 위해서 이 경우의 return값을 0으로 정의해 줘야 한다는 거다.

vector<int> v[100001];

// 기본적인 bfs, vector와 deque를 활용
int bfs(int start, int end) {
    deque<pair<int, int>> q;
    bool visit[100001];
    memset(visit, false, sizeof(visit));

    q.push_back(make_pair(start, 1));
    visit[start] = true;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop_front();
        int pos = cur.first;
        int length = cur.second;

        if (pos == end) {
            return length;
        }
        for (int i=0; i<v[pos].size(); i++) {
            int npos = v[pos][i];
            if (visit[npos]) continue;
            visit[npos] = true;
            q.push_back(make_pair(npos, length+1));
        }
    }
    return 0; // 쓰레기 값이 나오는 것을 막아주려면 q를 그냥 통과했을 때 기본 값을 주어야 한다.
}

 

수학적으로 계산하는 부분은 노트에서와 마찬가지로 그대로 구현했다. 

// 현재의 그래프 구조가 n개의 노드에 n-1개의 간선으로 이루어져 있기 때문에
    // 순환이 존재하지 않고 한 포인트에서 다른 포인트로 가는 경로가 유일하다는 것을 유념해 둬야함
    // 중간 심부름을 거쳐 최종 목적지 까지 도달하는 거리 (중간 심부름 2번 포함하여 1 빼줌)
    int start_m_f = bfs(s, c) + bfs(c, h) - 1;
    // 중간 심부름을 거치지 않고 최종 목적지까지 도달하는 거리
    int start_to_f = bfs(s, h);

    // 중복된 원소 갯수 계산
    // 최소경로로 심부름까지 진행했고, 최소 경로로 목적지까지 진행하기 때문에,
    // 유일한 경로에서 심부름을 거쳤다 가는 거리와 목적지 바로 가는 것의 차이는 중복된 노드 *2 갯수 만큼 차이가 난다
    // 노드를 계산할 때 중복없는 조합의 갯수를 구하고, 중복이 있는 부분에 대해서는 뒤집어서 노드 형성이 가능하므로 이 부분 더해준다.
    long long dup_point = (start_m_f - start_to_f)/2;
    long long non_dup_point = start_m_f - dup_point;
    long long ans = (non_dup_point*(non_dup_point-1) + dup_point *(dup_point+1))/2; // long long으로 받지 않으면 overflow 오답

    cout << ans << '\n';

 

 

 

 전체 코드는 다음을 참고하기 바란다. 

https://github.com/Koo82/Algotirhm/blob/main/BJ_25198.cpp

GitHub - Koo82/Algotirhm