[백준 13023] ABCDE

[백준 13023] ABCDE

문제 링크

#include "header.h"
using namespace std;
int N, M;
int visit[2001];
int answer;
vector <int> v[2001];
void input(){
    cin >> N >> M;

    for(int i=0; i<M; i++){
        int a = 0;
        int b = 0;
        cin >> a >> b;
        //그래프 생성
        v[a].push_back(b);
        v[b].push_back(a);
    }
}
void dfs(int idx, int cnt){
    if(cnt >= 5){
        answer = 1;
        return;
    }

    visit[idx] = 1;

    for(int there : v[idx]){
        if(visit[there]) continue;
        dfs(there, cnt+1);
    }

    visit[idx] = 0;
    
}
void solve(){

    for(int i=0; i<N; i++){
        if(!visit[i]){
            dfs(i, 1);
        }
        if(answer) break;
    }

    cout << answer << endl;

}

int main() {
    input();
    solve();

    return 0;
}

• dfs로 푸는 문제.
• 친구를 타고 들어가면서 총 센 친구 수가 N이 넘으면 break