[백준 5567 - C++] 결혼식 : BFS

www.acmicpc.net/problem/5567

5567번: 결혼식

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai< bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 

 

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

 

 

 

 

풀이

이 문제에서 가장 중요한 것은 친구관계는 양방향이라는 것이다.

예를들어, 친구 관계에 대한 입력이

3

2

1 2

3 2

이렇게 들어오는 경우, 단방향으로 생각한다면 쉽게 말해 1은 2를 친구로 생각하는데, 2는 1을 친구로 생각하지 않게되는것이다. 

다음 3 2 입력에서 역시 3은 2를 친구로 생각하나 2는 3을 친구로 생각하지않는다.

이 관계를 1 -> 2, 3->2라고 나타내면 3은 결혼식 초대를 받지 못한다. 2에겐 친구로 인정 받지 못하니까ㅠ

 

그렇다면 친구관계를 양방향으로 고려하면 어떻게 될까?

1과 2는 서로 친구이고 3과 2도 서로 친구이다,

1<->2, 2<->3인것이다. 이렇게 양방향으로 친구 관계를 고려해야 3도 결혼식에 제대로 초대받게 된다.

 

그래서 친구관계를 2차원 배열로 선언하여 1과2의 친구 관계의 경우 frd[1][2] = 1, frd[2][1] =1로 하여 양방향으로 친구관계를 고려해주었다!

또한 이미 초대하기로 한 친구를 표시하기 위한 1차원 배열을 만들어 초대하는 것으로 체크해준다.

처음에 큐에는 이미 상근이와 친구인 사람들을 넣어주고 하나씩 뽑으면서 그 친구의 친구들중 초대 받지 못한 사람들을 추가로 초대해주면 끝!

 

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

int frd[500][500];
int con[500];

int main(void){
    int n, m;
    int f1, f2;
    int F;
    int cnt=0;
    queue<int> q;
    
    scanf("%d", &n);
    scanf("%d", &m);
    
    con[0] = 1;
    for(int i=0; i<m; i++){
        scanf("%d %d", &f1, &f2);
        frd[f1-1][f2-1] = 1;
        frd[f2-1][f1-1] = 1;
        if(f1 == 1){
            q.push(f2-1);
            con[f2-1] = 1;
            cnt++;
        }
        if(f2 == 1){
            q.push(f1-1);
            con[f1-1] = 1;
            cnt++;
        }
    }
    while(!q.empty()){
        F = q.front();
        
        for(int i=1; i<n; i++){
            if(frd[F][i] == 1 && con[i] == 0){
                con[i] = 1;
                cnt++;
            }
        }
        q.pop();
    }
    printf("%d\n", cnt);
    
}