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

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

최소 5명의 사람이 연속적인 친구 관계를 가지는지 구하여라.

 

 문제에서 친구관계는 그래프의 간선으로 치환할 수 있으므로 그래프 문제로 생각하면

그래프에 깊이가 5인 경로가 존재하는지 구하여라.

로 요약할 수 있습니다.

---

시간복잡도 어림하기

DFS 알고리즘

 그래프의 깊이를 구해야하는 문제이므로 DFS 알고리즘을 사용할 수 있습니다. 이 문제에서는 그래프를 인접 리스트를 통해 구현할 수 있어 DFS 알고리즘의 시간복잡도는 O(N + M)입니다. 문제에서 N과 M은 모두 2000이므로 DFS 알고리즘은 4000의 시간복잡도를 가집니다. 이를 모든 노드에 대해 반복하면 2000 x 4000 = 8,000,000으로 제한 시간 내에 문제를 해결하기 충분한 수치입니다.

---

알고리즘 설계하기

 그래프의 탐색 경로의 깊이를 탐색하기 위해서는 가능한 모든 경로에 대해 그래프를 탐색해야 합니다. 따라서 한 노드를 방문한 후, 탐색을 진행하다가 다시 돌아왔을 때 방문처리를 취소해야 모든 경로를 탐색할 수 있습니다.(원상복구) 이를 기반으로 dfs를 설계해봅시다.

 dfs의 기본구조는 다음과 같습니다.

1. 현재 노드 방문처리
2. 현재 노드에서 이동 가능한 다음 노드 탐색
3. 다음 노드를 방문하지 않았다면, 다음 노드 탐색

 

 여기서 모든 경우의 수를 탐색하기 위해서는 3번 조건의 수정이 필요합니다. 위의 3번 조건에서는 한 번 방문한 노드는 다시 방문하지 않기 때문에 처음에 결정된 경로 한 번만 탐색을 진행합니다. 따라서 이를 다음과 같이 수정해야합니다.

3. 다음 노드를 방문하지 않은 경우,
3-1. 다음 노드 탐색 및 방문처리
2-2. 탐색 후 다음 노드 방문처리 취소

 이와 같이 다음 노드를 탐색하고 다시 돌아올 때, 방문처리를 취소해야 다른 노드에서 해당 노드를 방문할 수 있으므로 모든 경로를 탐색합니다.

 

 이 과정을 모든 노드를 시작점으로 하여 깊이가 5인 경로가 그래프에 있는지 확인합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<vector>
using namespace std;

int n, m, visited[2004], flag;
vector<int> adj[2004];
void dfs(int node, int depth){
    if(depth == 5){ //경로의 깊이가 5, 탐색 종료
        flag = 1; return;
    }
    for(int next : adj[node]){
        if(visited[next]) continue;
        visited[next] = 1; //다음 노드 방문처리
        dfs(next, depth + 1); //다음 노드 탐색
        visited[next] = 0; //다음 노드 방문처리 취소
    }
}
int main(){
	/*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    int from, to;
    for(int i = 0; i < m; i++){
        cin >> from >> to;
        /*양방향(무방향) 그래프*/
        adj[from].push_back(to);
        adj[to].push_back(from);
    }

    for(int i = 0; i < n; i++){
        visited[i] = 1; //시작 노드 방문처리
        dfs(i, 1);
        visited[i] = 0; //시작 노드 방문처리 취소
        if(flag) break; //결과를 찾은 경우 탐색 종료
    }
    cout << (flag == 0 ? 0 : 1);
    return 0;
}

 그래프에서 가능한 모든 경로를 탐색해야하기 때문에 방문처리를 하고, 취소하면서 모든 경로를 탐색합니다.

 여기서 main함수의 for 루프에 있는 if문을 사용하지 않으면 시간초과가 발생하는데, 시간초과가 발생하는 이유는 솔직히 잘 모르겠습니다. 개인적인 생각으로 결과를 찾지 못했을 때, 결국 모든 경로를 다 탐색하기 때문에 결과를 찾은 후 탐색을 조기 종료하는 것이 의미가 없다고 생각했는데 그게 아니었던 모양입니다...

---