결혼식

알고리즘 구분 : BFS

문제

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

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

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

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

예제 입력 1
6
5
1 2
1 3
3 4
2 3
4 5
예제 출력 1
3
예제 입력 2
6
5
2 3
3 4
4 5
5 6
2 5
예제 출력 2
0

문제 풀이

위 문제를 보면, "자신의 친구와 친구의 친구를 초대하기로 했다"라는 문장이 있다. 이 문장을 통해 BFS로 접근해야 겠다는 판단이 되었다. BFS로 구현하면서 visited를 boolean 자료형이 아닌 int 자료형으로 상근이를 기준으로 거리를 산정하여 해당 거리가 2를 초과하게 될 경우, 상근이의 친구의 친구를 넘어서는 것으로 판단하여 구현하기로 하였다.
맨 처음 문제를 풀 때, ai < bi를 보고, 단방향 그래프로 구현하여도 상관 없을 것으로 판단하여 단방향으로 BFS 조건을 거리 조건 0 이상 2 미만으로 설정하여 구현하여 제출하였으나, "틀렸습니다." 판정을 받았다.
두 번째로는 단방향 그래프에서 양방향 그래프로 변경하여 다시 제출하였으나, 이번에는 "메모리 초과" 판정을 받았다.
마지막으로, visited를 boolean 자료형으로 구현할 수 있는 방법을 생각해보았더니, 상근이의 친구들을 기준으로 바로 이중 반복문을 돌릴 경우, 친구의 친구들만 true값을 가지도록 visited 구현이 가능하다는 것을 파악하게 되었다. 그래서 처음엔 q.push(1); 이후 while(!q.empty())를 이용하여 상근이부터 BFS를 시작하였으나, 아래의 풀이와 같이 친구들을 기준으로 이중 반복문으로 구현하게 되었다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

int n, m, result;
vector<int> graph[501];
bool visited[501] = { false };
queue<int> q;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	q.push(1);
	visited[1] = true;
	for(int i = 0; i <= graph[1].size(); i++) {
		int now = q.front();
		q.pop();
		for(int j= 0; j < graph[now].size(); j++) {
			int next = graph[now][j];
			if(visited[next] == false) {
				visited[next] = true;
				q.push(next);
				result++;
			}
		}
	}
	
	cout << result << endl;
	
	return 0;
}

• 문제 출처 : https://www.acmicpc.net/problem/5567
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.