(C++) - 백준(BOJ) 13023번 : ABCDE

www.acmicpc.net/problem/13023

13023번: ABCDE

dfs문제입니다.

 

풀이방법

 1. 인접리스트로 친구관계를 만들어줍니다. 친구 사이니 양방향 그래프가 됩니다.

 

 2. dfs를 수행합니다. 확인하지 않는 친구사이들 중에 dfs가 5번 호출이 되었다는 뜻은 조건에 부합하다는 말입니다. ABCDE순으로 dfs가 호출되었다면 해당 관계가 존재한다는 뜻으로 1을 return해줍니다.

 

 3. 자신과 연결된 모든 친구관계를 확인했다면 자신을 통해 다른 친구관계를 확인할 수 있도록 자신을 체크했던것을 0으로 만들어줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
vector<int> graph[2001];
int ck[2001];
int dfs(int start,int cnt){
    if(cnt == 5) return 1;
    if(ck[start]) return 0;
    ck[start] = 1;
    int ans = 0;
    for(int i = 0; i < graph[start].size(); i++){
        int next = graph[start][i];
        if(ck[next]) continue;
        ans = max(ans,dfs(next,cnt+1));
    }
    ck[start] = 0;
    return ans;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int start, end;
        cin >> start >> end;
        graph[start].push_back(end);
        graph[end].push_back(start);
    }
    
    for(int i = 0; i < n; i++){
        memset(ck,0,sizeof(ck));
        ans = max(ans,dfs(i,1));
    }
    cout << ans <<'\n';   
}