[Baekjoon] 5567 결혼식

알고리즘 분류

구현

그래프 이론

문제 - https://www.acmicpc.net/problem/5567

-문제-

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

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

-입력조건-

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

-해결방법-

행렬(n+1,n+1)을 만든뒤, 친구인 관계를 입력 받는다. 이때, 1 2 이렇게 입력이 들어올 수도 있지만 2 1 이렇게 입력이 들어올 수 있기 때문에 

relation[a][b] =1 , relation[b][a] =1 로 행렬을 완성한다.

1행을 탐색하며 친구인 관계를 queue에 삽입

1은 다 탐색했으니 visited[1]=false로 상근이 뿐만아니라 탐색한 친구를 false로 만들어 탐색유무 표시 한다.

queue가 빌때까지 queue에 넣은 친구를 꺼내며 이 친구의 친구를 확인한다. visited도 확인

처음엔 vector<pair<int,int>>로 했다가 처음 경우의 수 때문에 틀림..ㅠㅠ

<소스코드>

#include <iostream> #include <vector> #include <queue> using namespace std; int main() { int n, m; cin >> n >> m; //vector<pair<int, int>> relation(m); vector<vector<int>> relation(n + 1, vector<int>(n + 1)); vector < bool > visited(n + 1,true); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; relation[a][b] = 1; relation[b][a] = 1; } int answer = 0; queue<int> Q; for (int i = 1; i <= n; i++) { if (relation[1][i] == 1) { visited[i] = false; Q.push(i); answer++; } } visited[1] = false; while (!Q.empty()) { int temp = Q.front(); Q.pop(); for (int i = 1; i <= n; i++) { if (relation[temp][i] == 1 && visited[i] == true) { visited[i] = false; answer++; } } } cout << answer << endl;     return 0; }