[BOJ] 13023 ABCDE

https://www.acmicpc.net/problem/13023

13023번: ABCDE

전형적인 dfs 문제이다. 모든 점을 인자로 넣어 dfs를 돌면서 한칸 옮겨갈 때 마다 cnt에 1을 더해주고 cnt가 5일 경우를 찾으면 dfs를 멈췄다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,M;
vector<int> v[2001];
bool flag=false;
bool check[2001];

void dfs(int now,int cnt){
    if(flag) return;
    if(cnt==5){
        flag=true;
        return;
    }
    check[now]=true;
    for(int i=0;i<v[now].size();i++){
        if(!check[v[now][i]]){
            dfs(v[now][i],cnt+1);
        }

    }
    check[now]=false;
}

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    cin>>N>>M;
    for(int i=0;i<M;i++){
        int from,to;
        cin>>from>>to;
        v[from].push_back(to);
        v[to].push_back(from);
    }
    for(int i=0;i<N;i++){
        if(flag) break;
        fill(&check[0],&check[N],false);
        dfs(i,1);
    }
    if(flag) cout<<1;
    else cout<<0;
    return 0;
}