[Gold V] ABCDE - 13023

[문제 위치]

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

[문제 풀이]

DFS 문제이며 백트래킹 문제이다.

모든 사람들을 돌며 DFS 5단계까지 들어갈 수 있는지 확인하고 5가 된다면 탐색 종류 및 참 반환 그렇지 않다면 방문하지 않은 노드로 표시하며 재탐색 여부를 열어놓는 백트래킹을 실시한다.

 

아래는 그 코드이다.

#include <iostream>
#include <vector>
#include <cstring>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector<int> people[2001]; // 친구 목록
bool visited[2001] = { 0 }; // 방문 여부

bool DFS(int start, int cnt) {
    visited[start] = true;
    cnt += 1;
    if (cnt == 5) {
        return true;
    }

    for (int next_node : people[start]) {
        if (!visited[next_node]) {
            if (DFS(next_node, cnt)) {
                return true;
            }
        }
    }
    visited[start] = false; // 백트래킹
    return false;
}

int main() {
    fastio;
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int P1, P2;
        cin >> P1 >> P2;
        people[P1].push_back(P2);
        people[P2].push_back(P1); // 친구 관계는 양방향
    }

    for (int i = 1; i <= N; i++) {
        memset(visited, 0, sizeof(visited)); // 방문 여부 초기화
        if (DFS(i, 0)) {
            cout << 1 << endl;
            return 0;
        }
    }

    cout << 0 << endl;
    return 0;
}