[BOJ 13023] ABCDE

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

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

제한

시간 제한	메모리 제한
2sec	512MB

---

풀이

총 $N$명의 사람 사이의 친구 관계가 주어질 때, $A-B-C-D-E$와 같이 $5$명이 일렬로 친구 관계를 맺고 있는 경우가 존재하는지 확인하는 문제다. 이를 그래프 관점에서 해석하면, 주어진 무방향 그래프에서 길이가 $4$인 단순 경로(Simple Path)가 존재하는지 찾는 문제로 변환할 수 있다.

사람의 수 $N$과 친구 관계의 수 $M$은 각각 최대 $2\,000$으로 주어지며, 시간 제한은 $2$초로 비교적 넉넉한 편이다. 하지만 모든 경로를 단순히 탐색하기에는 그래프의 구조에 따라 지수적인 시간 복잡도가 발생할 수 있으므로 주의가 필요하다. 다행히 우리가 찾아야 하는 경로의 길이는 $4$로 고정되어 있어, DFS 탐색를 활용하면 효율적으로 해결이 가능하다.

해결 과정은 다음과 같다.

1. 친구 관계를 인접 리스트(Adjacency List) 형태로 저장한다. 정점의 개수에 비해 간선의 수가 적은 편이므로 인접 행렬보다는 리스트를 사용하는 것이 메모리와 탐색 속도 면에서 유리하다.
2. 모든 정점을 시작점으로 하여 DFS 탐색을 수행한다.
3. DFS 함수는 현재 방문한 정점과 현재까지의 경로 길이(depth)를 매개변수로 받는다.
4. 이미 경로에 포함된 정점을 다시 방문하지 않도록 visit 배열을 사용하여 체크하고, 탐색이 끝나면 다시 체크를 해제하는 백트래킹 알고리즘을 적용한다.
5. 만약 탐색 도중 depth가 $4$에 도달한다면, 문제의 조건을 만족하는 $5$명의 친구 관계를 찾은 것이므로 즉시 탐색을 종료하고 $1$을 출력한다.

\[depth = 4\]

위 수식에서 알 수 있듯이, $A$에서 시작하여 $4$번의 간선을 더 거쳐 $E$까지 도달하는 순간이 정답을 찾는 시점이다. 전체 정점을 한 번씩 시작점으로 잡고 탐색을 수행하되, 한 번이라도 조건을 만족하면 조기에 종료하여 효율성을 높였다. 만약 모든 정점에 대해 탐색을 마쳤음에도 조건을 만족하는 경로를 찾지 못했다면 $0$을 출력한다.

소스코드

Github Link : Source Code

참고 알고리즘 : DFS 탐색