문제
BOJ에서 친구 관계는 양방향이다. N명의 사람과 M개의 친구 관계가 주어질 때, A-B-C-D-E 형태의 친구 체인(A와 B는 친구, B와 C는 친구, C와 D는 친구, D와 E는 친구)이 존재하는지 확인하라.
A, B, C, D, E는 모두 다른 사람이어야 한다.
입력
첫 번째 줄에 N과 M이 주어진다. (5 ≤ N ≤ 2,000, 1 ≤ M ≤ 2,000)
이후 M줄에 걸쳐 친구 관계 a, b가 주어진다. (0-indexed)
출력
A-B-C-D-E 친구 체인이 존재하면 1, 아니면 0을 출력한다.
예제
5 4
0 1
1 2
2 3
3 4출력:
1풀이
핵심 아이디어: 깊이가 5인 단순 경로(같은 노드를 두 번 방문하지 않는 경로)가 존재하는지 DFS + 백트래킹으로 확인한다. 각 노드를 시작점으로 DFS를 수행하여 깊이가 5에 도달하면 체인이 존재한다. 방문 처리를 할 때 백트래킹으로 방문 해제를 해야 다른 경로도 탐색 가능하다.
- N명의 인접 리스트를 구성한다.
- 각 노드 i를 시작점으로
dfs(i, 1)을 호출한다. - DFS에서 현재 깊이가 5이면
state = true로 설정하고 즉시 반환한다. - 현재 노드를 방문 처리 후, 방문하지 않은 이웃 노드를 재귀 탐색한다.
- 재귀 복귀 후 방문 해제(백트래킹)하여 다른 경로 탐색을 허용한다.
state가 true면 즉시 1을 출력하고 종료한다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Day318BOJ13023ABCDE {
static int N, M;
static boolean state = false;
static List<Integer>[] list;
static boolean[] check;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
list = new ArrayList[N];
for (int i = 0; i < N; i++) {
list[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list[a].add(b);
list[b].add(a);
}
solve();
br.close();
}
private static void solve() {
for (int i = 0; i < N; i++) {
check = new boolean[N];
dfs(i, 1);
if (state) {
System.out.println(1);
return;
}
}
System.out.println(0);
}
static void dfs(int idx, int d) {
if (d == 5) {
state = true;
return;
}
check[idx] = true;
for (int i : list[idx]) {
if (!check[i]) {
dfs(i, d + 1);
}
}
check[idx] = false;
}
}복잡도
- 시간: O(N × (N + M)) — 각 노드를 시작점으로 DFS 수행, 최악의 경우 N번 × (N+M)
- 공간: O(N + M) — 인접 리스트와 방문 배열