BOJ 실버1 5567번 결혼식 문제입니다.
상근이의 결혼식에 동기들 중 자신의 친구와 친구의 친구만을 초대하는 문제입니다.
다른 풀이들은 대부분 BFS로 거리를 이용해서 해결했습니다.
'친구의 친구의 친구의... 친구'같이 확인해야 하는 관계가 두 번 이상 이어진다면 BFS가 정석이겠지만
이 문제에서는 친구의 친구까지만 확인하면 돼서 저는 이중 for문을 이용해서 해결했습니다.
#include <iostream>
using namespace std;
int map[501][501]; // 친구 관계 저장
int invite[501]; // 초대할 학번 저장
int main()
{
int n, m;
int a, b;
int cnt = 0;
cin >> n >> m;
// 1 친구 관계 입력받기
for (int i = 0; i < m; i++)
{
cin >> a >> b;
map[a][b] = 1;
map[b][a] = 1;
}
// 2 초대할 사람 찾기
for (int i = 2; i <= n; i++)
{
if (map[1][i] == 1) // 상근이과 친구(1 고정)
{
invite[i] = 1;
for (int k = 2; k <= n; k++)
{
if (map[i][k] == 1) // 그 친구와 친구 (i 고정)
invite[k] = 1;
}
}
}
// 3 초대할 사람 수 구하기
for (int i = 2; i <= n; i++)
{
if (invite[i])
cnt++;
}
cout << cnt;
return 0;
}
상근이과 직접 친구이면서 다른 직접 친구와도 친구라면 두 번 초대하게 되므로
for문을 돌 때 바로 세지 않고 초대할 친구 배열에 저장했다가 마지막에 사람 수를 구합니다.
만약 for 문에서 바로 더해준다면,
입력이
5
3
1 3
1 4
3 4
일 때
6
5
1 2
1 3
3 4
2 3
4 5
3 (2, 3, 4)
6
5
2 3
3 4
4 5
5 6
2 5
0
10
10
4 10
7 10
3 7
6 8
1 7
1 6
1 5
1 9
2 4
3 8
7 (3, 5, 6, 7, 8, 9, 10)