백준 5567 결혼식

작성일 | In |

Problem : 결혼식

유형 : 그래프, DFS

해결 전략

  • 친구와, 친구의 친구 까지 초대가 가능하다.
    • 즉, 두 다리 건너의 친구까지는 초대가 가능하다.
    • 이것은 몇 다리 건너서 친구인지는 DFS의 깊이로 판단할 수 있다.
  • 상근이의 친구를 전부 방문해본다. depth 1
    • 이때 친구의 친구라서 방문했어도, 만나본다.
  • 상근이의 친구의 친구를 방문해본다 depth 2

주의할 점

  • 친구가 상근이를 초대할 수 있다.
    • 이 부분을 DFS전 처리한다.
  • 상근이의 친구는 일단 전부 다 방문해본다. (방문한적이 있어도)
  • 대신 방문이 된 경우에는 또 초대하진 않는다.

풀이

인접리스트를 세팅한다.

  • 양방향으로 세팅한다.

상근이의 친구를 방문한다.

  • 초대된적이 없으면 초대한다.
  • 초대된적이 있으면, 초대는 하지 않되, 친구의 친구를 찾으러가본다.

상근이의 친구의 친구를 방문한다.

  • 초대된적이 없으면 초대한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

int n, m;
bool isInvited[502];
vector<int> node[502];

int answer = 0;

void inviteFriend(int inviter, int depth) {
    if (depth == 2) return;

    for (int friendNum : node[inviter]) {
        if (!isInvited[friendNum]) {
            isInvited[friendNum] = true;
            answer++;
        }
        inviteFriend(friendNum, depth + 1);
    }
}

void solve() {
    cin >> n;
    cin >> m;
    while (m--) {
        int s, e;
        cin >> s >> e;
        node[s].push_back(e);
        node[e].push_back(s);
    }

    isInvited[1] = true;
    inviteFriend(1, 0);
    cout << answer << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    solve();

    return 0;
}

피드백

  • 8개월 만에 다시 풀어봤는데, 풀이가 더 복잡해졌다.
    • 그래프 관련 문제를 다시 수련해야겠다. 12-04