결혼식


작성일 : 2017-01-11 02:01:34
조회수 : 446



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


이 문제는 사람 A와 사람 B가 친구라면, 둘 사이의 거리는 1이라고 정의한 다음 각 친구관계를 모두 기록하여 최단거리를 찾는 문제로 바꾸어 풀 수 있습니다.


만약 A, B가 친구이고 C, B가 친구라면 $dist[A][B]=1$ 이고 $dist[C][B]=1$이 되어 $dist[A][C] = dist[A][B]+dist[B][A]$ 를 수행할 수 있게 됩니다.


자기 자신에 대해서 최단거리를 구하면 되기 때문에 이 문제는 다익스트라 알고리즘을 이용할 수 있습니다. 다익스트라는 인접 행렬을 이용한 $O(n^2)$ 알고리즘과, 인접 리스트를 이용한 로그 시간 복잡도를 가지는 알고리즘 2개가 있는데, 소스코드에서는 인접 리스트를 이용한 다익스트라 소스를 올리겠습니다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
typedef long long ll;
using namespace std;

class Node
{
public:
    int d, c;
    Node() {}
    Node(int d, int c) :d(d), c(c) {}
    bool operator < (const Node &n) const
    {
        return c > n.c;
    }
};
vector<vector<Node> >v;
int dist[501];
bool visit[501];
int main()
{
    ios::sync_with_stdio(false);

    int n, m, ans = 0;
    cin >> n >> m;
    v.resize(n + 1);
    fill(dist, dist + n + 1, 2e9);
    for (int i = 0; i < m; i++)
    {
        int a, b;

        cin >> a >> b;
        v[a].push_back({ b,1 });
        v[b].push_back({ a,1 });
    }
    priority_queue<Node> pq;
    pq.push({ 1,0 });
    dist[1] = 0;
    while (!pq.empty())
    {
        auto here = pq.top();
        pq.pop();

        if (visit[here.d]) continue;
        visit[here.d] = true;
        for (auto there : v[here.d])
        {
            if (dist[there.d] > dist[here.d] + there.c)
            {
                dist[there.d] = dist[here.d] + there.c;
                pq.push({ there.d,dist[here.d] });
            }
        }
    }
    for (int i = 2; i <= n; i++) if (dist[i] <= 2) ans++;
    cout << ans;
}

결혼식 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글