문제
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을 출력한다.
풀이
친구 관계 그래프에서 길이 4짜리 단순 경로가 존재하는지만 보면 된다. 즉 한 정점에서 시작해 깊이가 5가 되는 DFS가 가능한지 찾으면 된다.
코드에서는 현재 정점을 방문 처리하고 인접한 정점으로 재귀를 내려가며 깊이를 증가시킨다. 깊이가 조건에 도달하면 바로 성공으로 종료하고, 아니면 방문을 되돌리며 다른 경로를 시도한다.
그래프 전체를 다 분석할 필요 없이, 길이 4의 단순 경로 존재 여부만 찾는 백트래킹 DFS 문제다.
코드
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] friends;
static boolean[] visited;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
friends = new ArrayList[N];
visited = new boolean[N];
for (int i = 0; i < N; i++)
friends[i] = new ArrayList<>();
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
friends[a].add(b);
friends[b].add(a);
}
boolean found = false;
for (int i = 0; i < N; i++) {
if (solve(i, 0)) {
found = true;
break;
}
}
if (found) System.out.println(1);
else System.out.println(0);
}
static boolean solve(int cur, int cnt) {
if (cnt == 4)
return true;
visited[cur] = true;
for (int next : friends[cur])
if (!visited[next])
if (solve(next, cnt + 1))
return true;
visited[cur] = false;
return false;
}
}복잡도
- 시간 복잡도: 깊이 제한 DFS를 각 정점에서 시작하므로 최악의 경우 이다.
- 공간 복잡도: 그래프와 방문 배열, 재귀 스택을 사용하므로 이다.
마무리
결국 필요한 것은 깊이 5짜리 단순 경로 하나다. DFS로 내려가며 길이만 확인하면 되는 비교적 직선적인 탐색 문제다.
