BOJ 13023 ABCDE

작성일 | In |

Problem : ABCDE

유형 : 그래프, DFS

해결 전략

문제 자체를 이해하는데 꽤나 애를 먹었다.
문제에서 요구하는것은 N 명에 따른

  • A는 B와 친구다.
  • B는 C와 친구다.
  • C는 D와 친구다.
  • D는 E와 친구다.

조건 이 만족하는지를 찾는것이다.

친구쌍이 4개이상이 나오는가?

라고 해석이 가능하다.

그렇다면 친구 쌍4개를 어떻게 찾는가?

친구가 없는 사람과 짝을 짓는 과정이, 연속적으로 4회 이상이 가능한지를 확인한다.

  • A가 B와 짝을 맺는다.
  • B는 C와 짝을 맺는다.
    • B는 A와 짝을 맺으려고 시도해볼 수 있다.
    • 하지만 A는 이미 짝이 있으므로 넘어간다.

주의할 점

  • 처음에 찾으러 들어갈때, 자기 자신에 표시를 해주고 들어가야한다.

풀이

인접 리스트를 세팅한다.

  • 양방향 그래프로 연결시킨다.

DFS를 진행한다.

  • 친구가 없던놈이면 짝을 짓는다.
  • 짝이된 사람은 다른 짝을 찾으러 다시 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
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

vector<int> human[2002];
bool visit[2002];
int n, m;
bool find_answer;

void dfs(int cur, int depth) {
    if (find_answer) return;

    if (depth == 4) {
        find_answer = true;
        return;
    }

    for (auto nxt : human[cur]) {
        if (visit[nxt])continue;
        visit[nxt] = true;
        dfs(nxt, depth + 1);
        visit[nxt] = false;

        if (find_answer) return;
    }
  
}

int solve() {
    for (int i = 0; i < n; ++i) {
        visit[i] = true;
        dfs(i, 0);
        visit[i] = false;
        if (find_answer) return 1;
    }
    return 0;
}

void input() {
    cin >> n >> m;
    int a, b;
    while (m--) {
        cin >> a >> b;
        human[a].push_back(b);
        human[b].push_back(a);
    }
}

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

    input();
    cout << solve() << "\n";

    return 0;
}

피드백

없음