[BOJ 5567 / C++] 결혼식 (그래프)

문제링크: https://www.acmicpc.net/problem/5567

 

> 방법 1. DFS

1-1. 코드

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>>& adj, vector<int>& dist, int cur, int depth) {
    for (int nxt : adj[cur]) {
        int nd = depth + 1;
        if (nd > 2) continue;
        if (nd > dist[nxt]) continue;
        dist[nxt] = nd;
        dfs(adj, dist, nxt, depth+1);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n+1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> dist(n+1, INT_MAX);
    
    dist[1] = 0;
    dfs(adj, dist, 1, 0);

    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (dist[i] <= 2) cnt++;
    }
    cout << cnt;
}

 

 

1-2. 시간복잡도

인접리스트 그래프의 dfs 순회 시간복잡도는 O(v+e)이고, 여기서 v = 500, e = 10000이므로 10500 < 10^8 이므로 시간제한 1초 안에 통과 가능하다.

 

 

1-3. 분석

여기서는 그냥 vis 배열을 사용하면 안되고 dist 배열을 사용해야한다. 이유는 dfs를 사용하면 깊이 우선으로 들어가므로 경로가 더 긴쪽을 먼저 탐색하고 vis를 true로 갱신하기 때문이다. 따라서 dist 배열을 놓고 반드시 더 짧은 경로가 있는지 검사를 해야한다. 그래서 이 문제는 dfs로 풀면 실수할 여지가 많고 BFS로 푸는 것이 좀 더 좋다.

 

 

> 방법 2. BFS

2-1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n+1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    int cnt = 0;
    vector<int> dist(n+1, -1);
    queue<int> Q;
    
    Q.push(1);
    dist[1] = 1;
    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        
        if (dist[cur] > 2) continue;

        for (int nxt : adj[cur]) {
            if (dist[nxt] > 0) continue;
            dist[nxt] = dist[cur] + 1;
            Q.push(nxt);
            cnt++;
        }
    }
    
    cout << cnt;
}

 

 

2-2. 시간복잡도

시간복잡도는 인접리스트에서 DFS와 BFS가 모두 O(v+e)로 동일하므로 마찬가지로 시간제한 1초 내에 통과 가능하다.

 

 

2-3. 분석

BFS로 풀때는 dist 배열을 놓거나 아니면 queue<pair<int, int>>로 node와 depth를 저장할 수 있다. dist 배열을 사용하는 것이 좀 더 범용적이므로 dist 배열을 사용한다. dist 배열은 -1로 초기화 해두고 dist[nxt] > 0이면 이미 방문했다는 뜻이다. 친구의 수를 세야하므로 cnt는 큐에 1을 push할 때는 증가시키지 않아아하고 nxt들을 큐에 push할 때만 cnt를 증가시킨다.