[백준 13023 - C++] ABCDE : DFS

www.acmicpc.net/problem/13023

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을 출력한다.

 

풀이

이 문제는 처음에 시간 초과가 났다ㅠㅠㅠ 시간초과를 방지하려고 처음부터 벡터로 친구관계를 저장했는데도 시간초과라니...

2번정도 시간초과를 받고 나니까 안되겠다 싶어서 5명이 친구인걸 찾으면 원래는 재귀를 다시 되돌아 나와야하는데

그 위치에서 1을 출력하고 exit(0);으로 그냥 종료시켜버렸다.

혹시 이방법 말고 다른 방법이 있으면 댓글 부탁드립니다....

 

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector<vector<int>> frien;
int visit[2000];
int cnt;


void dfs(int s, int n);

int main(void){
    int n, m;
    int f_a, f_b;
    
    scanf("%d %d", &n, &m);
    frien.resize(n);
    for(int i=0; i<m; i++){
        scanf("%d %d", &f_a, &f_b);
        frien[f_a].push_back(f_b);
        frien[f_b].push_back(f_a);
    }
    
    for(int i=0; i<n; i++){
        cnt = 0;
        dfs(i, n);
    }
    printf("0\n");
}

void dfs(int s, int n){
    int there;
    cnt++;
    if(cnt == 5){
        printf("1\n");
        exit(0) ;
    }
    
    visit[s] = 1;
    for(int i=0; i<frien[s].size(); i++){
        there = frien[s][i];
        if(visit[there] == 1)
            continue;
        dfs(there, n);
    }
    cnt--;
    visit[s] =0;
}