[백준] (C++) 5567 - 결혼식

BOJ 실버1 5567번 결혼식 문제입니다.

상근이의 결혼식에 동기들 중 자신의 친구와 친구의 친구만을 초대하는 문제입니다.

문제 보기

백준 5567

접근

다른 풀이들은 대부분 BFS로 거리를 이용해서 해결했습니다.
'친구의 친구의 친구의... 친구'같이 확인해야 하는 관계가 두 번 이상 이어진다면 BFS가 정석이겠지만
이 문제에서는 친구의 친구까지만 확인하면 돼서 저는 이중 for문을 이용해서 해결했습니다.

문제 풀이

- 친구 관계를 이차원 배열에 1로 표현해서 전부 입력을 받습니다
- 1(상근이)과 친구인 학번(i)을 초대합니다
- 친구인 학번(i)과 친구인 학번(k)도 초대합니다

코드

#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;
}

1. 한 줄 씩 입력받으면서 map에 양방향으로 넣어줍니다.
2. map[1][i]를 보면서 상근이와 친구인 동기를 찾으면 invite[i]를 1로 바꿔주고,
   map[i][k]를 다시 보면서 그 친구와 친구인 동기를 찾으면서 invite[k]를 1로 바꿔줍니다.
3. invite 배열을 돌면서 1인 개수를 세어줍니다.

주의할 점

상근이과 직접 친구이면서 다른 직접 친구와도 친구라면 두 번 초대하게 되므로
for문을 돌 때 바로 세지 않고 초대할 친구 배열에 저장했다가 마지막에 사람 수를 구합니다.

만약 for 문에서 바로 더해준다면,
입력이

5
3
1 3
1 4
3 4

일 때

• 바깥 for 문에서 (map[1][3] == 1)이므로 3을 초대해 cnt = 1
• 안쪽 for 문에서 (map[3][4] == 1)이므로 4를 초대해 cnt = 2
• 바깥 for 문에서 (map[1][4] == 1)이므로 4를 또 초대해 cnt = 3이 되어 오류 발생

입출력 예시

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)