[백준 13023번] ABCDE (C++)

문제링크 : https://www.acmicpc.net/problem/13023

13023번: ABCDE

#include <bits/stdc++.h>
using namespace std;
#define ll long long

bool check;
vector<int> v[2000];
bool visited[2000];

void dfs(int i, int depth)
{
    if(depth == 4)
    {
        check = true;
        return;
    }

    visited[i] = true;  //방문처리

    for(int index = 0; index < v[i].size(); index++)
    {
        if(!visited[v[i][index]])
        {
            dfs(v[i][index], depth + 1);
        }
    }

    visited[i] = false;  //다음 탐색을 위해 원상복귀
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   
    int N, M, A, B;
    cin >> N >> M;

    for(int i=0; i<M; i++)
    {
        cin >> A >> B;
        v[A].push_back(B);
        v[B].push_back(A);
    }

    for(int i=0; i<N; i++)
    {
        dfs(i, 0);
        if(check) break;
    }

    cout << check;

    return 0;
}

깊이 우선 탐색 (dfs) 문제이다.

탐색을 하면서 처음 방문 처리를 할 때, 해당 값에 대한 탐색을 마치고 나서 방문 처리를 다시 원상복귀해줘야 한다.

그렇지 않으면 다음 값에 대한 탐색을 할 때 영향을 미친다.