[C++] BOJ 5567번 : 결혼식

 

 

 

https://www.acmicpc.net/problem/5567

 

문제 3줄 요약

 

1. 상근이는 결혼식에 자신의 친구 + 친구의 친구까지만 초대한다.

2. 친구의 친구의 친구는? 안된다.

3. 친구 관계 리스트를 보고 몇 명을 초대해야할 지 구해보자!

 

---

 

C++를 공부를 시작한지 얼마 되지 않아

아직 알고리즘 문제푸는게 익숙하지 않다고 느껴

다시 차근차근 푼 문제들을 블로그에 작성해야겠다.

 

 

처음에는 재귀 DFS를 사용하여 문제에 접근했는데,

Depth 처리가 생각보다 쉽지 않다고 느껴서

BFS로 바꿔서 풀었다.

 

제출한 코드가 길지 않으니

일단 필자의 데이터 입출력 부분부터 확인해보자!

 

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

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

    while(m--)
    {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    bfs(1);

    int ans=0;
    for(int i=1; i<501; i++)
    {
        if(visited[i]>1 && visited[i]<=3) ans++;
    }

    cout << ans;

    return 0;
}

 

 

 

Python으로 문제 풀 때에도

입출력 관련하여 속도 개선을 위한 코드가 필요했었는데,

C++에서 또한 마찬가지로 존재했다.

 

간단히 설명하자면,

2번 줄은 C++과 C 형식 중 C++ 형식만 사용함으로 설정하고

3번 줄은 입력 받을 때의 버퍼 관련 개선을 통해 입출력 시간을 개선 시킨다.

 

이 부분을 작성하지 않으면,

많은 백준 문제에서 시간 초과를 만나게 된다..ㅠ

 

 

 

다시 본론으로 돌아가서

상준이의 동기의 수는 n,

친구 관계 리스트에는 m개의 친구 관계가 존재한다.

 

입력을 차례대로 받아주고

친구 관계 리스트를 vector에 담는다.

 

 

 

한쪽만 친구라고 생각하는 아픈 현실이 있을 수 있지만,

문제에서는 서로가 친구라고 한다.

 

따라서 양방향으로

vector에 담아주는 것을 볼 수 있다.

 

이후 BFS를 들어간다..!

여기서 1은 상준이 임을 의미한다.

 

void bfs(int n)
{
    queue<int> q;
    q.push(n);
    visited[n]=1;

    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        for(int next : adj[cur])
        {
            if(!visited[next]){
                visited[next] = visited[cur]+1;	// 나와 상준이는 몇 다리 친구?
                q.push(next);
            }
        }
    }
}

 

 

일반적인 BFS와 코드는 동일하다.

 

Queue에 상준이부터 체크를 하며,

상준이의 친구들을 전부 Queue에 넣어준다.

 

여기서 상준이와 몇 다리 건너야 친구인지 체크하기 위해

방문 표시를 단순히 True가 아닌

내 이전의 친구와 상준이가 몇 다리인지 (=Detph) 받아와서

+1을 한 값을 넣어 주도록 한다.

 

BFS가 끝난 후

visited 배열에 담긴 친구들과 상준이의 Depth를 살펴보며

2 (상준이 친구), 3 (친구의 친구)를 몇 명인지 세어 출력하면....

 

 

 

 

정답!

 

전체 코드는 아래와 같다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> adj[501];
int visited[501];

void bfs(int n)
{
    queue<int> q;
    q.push(n);
    visited[n]=1;

    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        for(int next : adj[cur])
        {
            if(!visited[next]){
                visited[next] = visited[cur]+1;
                q.push(next);
            }
        }
    }
}

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

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

    while(m--)
    {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    bfs(1);

    int ans=0;
    for(int i=1; i<501; i++)
    {
        if(visited[i]>1 && visited[i]<=3) ans++;
    }

    cout << ans;

    return 0;
}

 

---

 

문제 자체가 어렵진 않지만

위에서 언급했듯 Python으로 준비를 해오다

C++로 다시 풀다보니 어려우면서도..

더 편한 부분도 많이 있는 것 같다.

 

끝!