[백준 13023] ABCDE C++

문제

백준 13023 ABCDE C++

13023번: ABCDE

풀이

깊이가 4이상인 노드가 있는지 확인하는 문제입니다.

각각의 노드에서 DFS를 실행하여 깊이가 4가 이상이 되는지 확인합니다.

소스 코드

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> v[2000];
bool visited[2000];
bool ispossible;
 
void dfs(int node, int depth) {
    if (depth == 4) {
        // 깊이가 4가 되면 ABCDE를 만족한다.
        ispossible = true;
        return;
    }
    visited[node] = true;
    // DFS
    for (int i = 0; i < v[node].size(); i++) {
        int next = v[node][i];
        if (!visited[next] && !ispossible) {
            dfs(next, depth + 1);
        }
    }
    visited[node] = false;
}
 
int N, M;
int main() {
    cin >> N >> M;
    // 그래프 처리
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 0; i < N; i++) {
        dfs(i, 0);
        if (ispossible) {
            break;
        }
    }
    cout << ispossible;
    return 0;
}