문제 푼 날짜 : 2021-09-29

문제

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

접근 및 풀이

bfs 또는 dfs로 풀 수 있는 문제였다.
상근이와 동기들의 관계를 인접리스트로 나타내었고, 상근이와 친구, 친구의 친구까지 초대하기 때문에 dfs로 그래프를 탐색하다가 깊이가 2일 때(상근이가 0, 상근이 친구가 1, 상근이 친구의 친구가 2) 가지치기를 해주었다.

최근에 bfs를 잘 안써서 그런지 문제를 보자마자 dfs가 먼저 떠올라서 dfs로 구현했는데, bfs로도 구현해봤다.

코드(DFS)

// 백준 5567번 : 결혼식
#include <iostream>
#include <vector>

using namespace std;

vector<int> v[501];
int visited[501] = { false, };
int ans = 0;

void dfs(int now, int depth) {
    if (depth == 2) {
        return;
    }

    for (int i = 0; i < v[now].size(); i++) {
        int next = v[now][i];
        visited[next] = true;
        dfs(next, depth + 1);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    while (m--) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    visited[1] = true;
    dfs(1, 0);

    for (int i = 1; i <= n; i++) {
        if (visited[i]) {
            ans++;
        }
    }   
    cout << ans - 1;
    return 0;
}

코드(BFS)

// 백준 5567번 : 결혼식
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int n, m, ans = 0;
    cin >> n >> m;

    vector<int> v[501];
    int visited[501] = { false, };

    while (m--) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    queue<pair<int, int>> q;
    q.push(make_pair(1, 0));
    visited[1] = true;

    while (!q.empty()) {
        int now = q.front().first;
        int depth = q.front().second;
        q.pop();

        if (depth == 2) {
            continue;
        }

        for (int i = 0; i < v[now].size(); i++) {
            int next = v[now][i];
            if (visited[next]) {
                continue;
            }
            visited[next] = true;
            ans++;
            q.push(make_pair(next, depth + 1));
        }
    }
    cout << ans;
    return 0;
}

결과

피드백

역시 알고 있던 알고리즘이라도 안쓰다보면 까먹게 된다... 더 부지런히 문제를 풀어야겠다.