[BOJ] #13023 ABCDE

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

13023번: ABCDE

---

인접리스트 형태로 주어진 그래프에서 Depth가 4 이상인 정점이 존재하는지 판별하는 문제이다. 이를 해결하려면 DFS 탐색에 이어 백트래킹 기법을 활용하여 해결해야한다.

 

백트래킹 Back Tracking 이란?

해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법을 말한다. 

 

따라서, DFS 방식으로 정점들을 순차적으로 탐색하며 non-promising한 정점들은 제외시키고 백트래킹 기법을 사용하여 제외하기 이전의 시퀀스로 다시 돌아가서 promising한 정점이 나오는 순간 탐색을 종료하고 조건에 맞게 출력하면 된다. 그리고 전체적으로는 아래의 매커니즘을 따른다.

1. 입력으로 주어지는 친구 관계를 인접리스트 형태로 그래프를 구성한다. 이때, 친구 관계이므로 방향성과 가중치가 없는 그래프 형태로 구성한다.
2. 순차적으로 정점들을 탐색하며 Depth가 4가 되는 지점들을 DFS를 이용하여 탐색해 나간다. 이때, DFS 함수의 인자에는 출발지점과 함께 Depth를 나타내는 cnt인자도 같이 전달하여 호출한다.
3. Depth가 4가 되는 지점을 찾은 경우, flag를 true로 바꿔주고 그 즉시 함수를 종료한다. 그리고 flag의 결과값에 따라 적절한 출력을 해주면 된다.
* 주의할 점은, 한번 DFS 탐색 후 다시 돌아와서 탐색을 진행할 때 방문여부는 false 가 되어야한다. 그래야 다른 사람을 기준으로 DFS 탐색을 진행할 때 그 사람을 다시 방문할 수 있다.

---

#include <iostream>
#include <vector>

#define MAX 2002

using namespace std;

int V,E;
vector<int> Graph[MAX];
bool visited[MAX] = { false };
bool flag = false;

void DFS(int start, int cnt) {
    if (cnt==4) {
        flag = true;
        return;
    }

    visited[start] = true;

    for (int i=0; i<Graph[start].size(); i++) {
        int idx = Graph[start][i];

        if (!visited[idx]) {
            DFS(idx, cnt+1);

            visited[idx] = false;
        }
    }
}

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

    cin >> V >> E;
    for (int i=0; i<E; i++) {
        int a,b;
        cin >> a >> b;

        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }

    for (int i=0; i<V; i++) {
        if (!visited[i]) {
            DFS(i,0);
            visited[i] = false;
        }

        if (flag) {
            cout << 1 << '\n';
            return 0;
        }
    }

    cout << 0 << '\n';

    return 0;
}