[C++] 백준 13023번 ABCDE - DFS, 백트래킹, 그래프

🔍 문제 요약

• 문제 링크: 백준 13023번 - ABCDE
• 주요 태그: DFS, 백트래킹, 그래프 탐색

---

💡 문제 분석

• 총 N명(0 ~ N-1)이 참가한 알고리즘 캠프에서 친구 관계가 M개 주어진다.
• 관계 A-B-C-D-E와 같은 연속된 5명의 친구 관계가 존재하는지 확인해야 한다.
  • A-B 
  • B-C
  • C-D
  • D-E

---

🔑 아이디어

• DFS를 활용하여 모든 노드에서 깊이 4까지 탐색한다. (간선 4개)
• 경로 탐색 중 동일한 사람을 중복해서 방문하지 않기 위해 visited[] 배열을 활용
• 깊이 4에 도달하면 즉시 종료하도록 flag 사용
• 탐색을 마친 후에는 visited[]를 원래 상태로 복구 (백트래킹)

---

🧩 풀이 전략

1. 인접 리스트 방식의 그래프 방식으로 푼다.
2. 모든 노드에서 DFS를 시작하면서 깊이 0부터 탐색
3. 방문한 노드는 visited[] = 1 , 탐색 종료 시 visited[] = 0 (다시 탐색하기 위함, 백트래킹)
4. DFS 중 depth == 4가 되는 순간, 바로 flag = true 후 탐색 중단
5. flag가 true이면 1 출력, 아니면 0 출력

---

📦 예제 입력 & 출력

• 입력:

5 4
0 1
1 2
2 3
3 4

• 출력:

1

• 입력:

6 5
0 1
0 2
0 3
0 4
0 5

• 출력:

0

---

🖥️ 코드

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

vector<int> graph[2001];
bool visited[2001];
bool flag = false;

void dfs(int start, int depth) {
    if (flag) return;
    if (depth == 4) {
        flag = true;
        return;
    }
    visited[start] = true;
    for (int next : graph[start]) {
        if (!visited[next]) {
            dfs(next, depth + 1);
        }
    }
    visited[start] = false; // 백트래킹
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 0; i < n; i++) {
		fill(visited, visited + n, 0);
        dfs(i, 0);
		if (flag) break;
    }
    cout << (flag ? 1 : 0);
    return 0;
}

---

✅ 검증 및 테스트

• DFS 깊이 4까지만 탐색 → 성능 최적화
• 백트래킹으로 다른 경로 탐색 가능
• 중복 방문 없이 단순 경로만 추적

---

⏱️ 시간복잡도

• 최대 노드 수: 2000
• DFS 깊이 제한: 5
• 시간복잡도: O(N * 4!) 수준 → 최대 약 수십만 연산 → ✅ 2초 제한 충분

---

✨ 결론

• 이 문제는 단순한 DFS처럼 보여도, 종료 조건 관리와 백트래킹 구현이 핵심이다.
• visited[] 관리를 잘못하면 틀릴 수 있으므로, depth 조건과 visited 백트래킹을 명확히 알자.