[BOJ] 13023 : ABCDE

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다.

사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

 

• A는 B와 친구다.

• B는 C와 친구다.

• C는 D와 친구다.

• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

 

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

 

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

 

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

 

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

 

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

 

CODE

#include <bits/stdc++.h>

using namespace std;

int N, M;
bool ans;

vector<int> graph[2000];
bool visited[2000];

void dfs(int from, int depth)
{
    if(depth == 5) 
    {
        ans = true;
        return;
    }

    for(int to : graph[from])
    {
        if(!visited[to] &&!ans)
        {
            visited[to] = true;
            dfs(to, depth + 1);
            visited[to] = false;    
        }
    }
}

void solve()
{
    for(int i = 0; i < N; i++)
    {
        if(!ans)
        {
            visited[i] = true;
            dfs(i, 1);
            visited[i] = false;
        }
    }
    cout << ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    for(int i = 0, from, to; i < M; i++)
    {
        cin >> from >> to;
        graph[from].push_back(to);
        graph[to].push_back(from);
    }
    solve();
}

 

COMMENT

 문제가 거창해 보이지만 그래프상에서 일렬로 연결된 5개의 정점이 있는가를 묻는 문제이다. 

 모든 정점을 시작점으로 DFS를 시작하여 시작점으로부터 깊이가 5인 정점이 존재하는지 탐색해야 하며, 만약 존재한다면 탐색을 멈추고 답을 출력해주면 된다. 위 코드에서 일반적인 DFS와 다른 점이 있는데, 시작점으로부터 다른 한 정점까지의 최장경로를 구해야 하기 때문에 한번 탐색한 정점을 또다시 탐색할 수도 있다는 것이다. 시간복잡도는 대략 O(N*(N+M)*depth)이고, 본 문제에서 depth=5, N <= 2000, M<=2000이므로 시간제한이 빡빡한 편이라 효율적으로 구현해야 한다.  따라서 가지치기를 통하여 적절히 빠져나와야 하며, 그렇지 않으면 시간초과에 걸릴 수 있다.

 

 

도움이 되셨다면 공감 꾸욱! 부탁드립니다 ~~!!😊