[백준] 5567번 결혼식

문제: 5567번: 결혼식

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>

using namespace std;

vector<vector<int>> persons(501);
vector<bool> visit(501);

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

    int n; // 동기의 수
    cin >> n;
    int m; // 리스트의 길이
    cin >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        persons[a].push_back(b);
        persons[b].push_back(a);
    }
    queue<pair<int, int>> nexts;
    nexts.push({ 1, 0 }); // 상근이
    visit[1] = true; // 방문표시
    int ans = 0;
    while (!nexts.empty()) {
        pair<int, int> cur = nexts.front();
        nexts.pop();

        if (cur.second > 0 && cur.second <= 2) {
            ans++;
        }

        if (cur.second < 2) {
            for (int next : persons[cur.first]) {
                if (visit[next]) continue;

                nexts.push({ next, cur.second + 1 });
                visit[next] = 1; // 방문표시!
            }
        }
    }
    cout << ans;

    return 0;
}

 

그냥 그래프에 BFS 적용하면 쉽게 해결할 수 있는 문제 ~_~

 

식장에 초대할 수 있는 경우는 최대 상근이의 친구의 친구까지로 제한된다. 3다리 건너 아는 사람이면 ans 에 반영해주면 안 됨!!

 

그래서 나는 queue 에 pair<int, int> 타입의 요소를 넣어서 관리하도록 했다. first 는 정점 번호, second 는 현재 정점으로 오는데 밟은 스텝 수를 저장하도록 했다.

 

만약 현재 정점까지 오는데 걸린 스텝이 2이하면 ans++ 을 해주도록 했다. 만약 스텝이 2가 됐다면 이제 내 다음으로 이어진 친구는 상근이가 초대할 수 없는 친구니까 if 문을 통해 거르도록 했다.