[백준] 13023_ABCDE C++

16 Dec 2023 in Study on Coding Test

DFS를 이용해보는 문제

정답제출코드

#include <iostream>
#include <vector>

using namespace std;

int N, M;
bool flag = false;
vector<int> v[2000];
bool visited[2000];

void backtrack(int node, int depth)
{
    if (depth == 4)
    {
        flag = true;
        return;
    }
    visited[node] = true;

    for (size_t i = 0; i < v[node].size(); ++i)
    {
        int next = v[node][i];
        if (!visited[next] && !flag)
            backtrack(next, depth + 1);
    }
    visited[node] = false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    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)
    {
        backtrack(i, 0);
        if (flag)
            break;
    }
    
    if (flag)
        cout << 1;
    else
        cout << 0;

    return 0;
}

DFS를 이용하면 되겠다는 생각했다.

문제는, A-B / B-C / C-D / D-E 관계를 어떻게 추출하냐였던 것 같아서 고민했는데,

예제 문제를 보니 순서를 지킬 필욘 없이 그냥 ABCDE가 전부 친구면 된다는 이야기 같았다.

그래서 코드를 위와 같이 짜서 해결하였다.