문제
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을 출력한다.
예제 입력 1
5 4
0 1
1 2
2 3
3 4
예제 출력 1
1
예제 입력 2
5 5
0 1
1 2
2 3
3 0
1 4
예제 출력 2
1
예제 입력 3
6 5
0 1
0 2
0 3
0 4
0 5
예제 출력 3
0
예제 입력 4
8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7
예제 출력 4
1
문제 이해
- 문제에서 나오는 A, B, C, D, E 총 5명의 친구 관계를 조건은 시작 노드로부터
depth가 4인 관계를 만족하는 관계이다. 즉, 그래프의 깊이가 4가 된다면 1을 출력하고, 아니면 0을 출력해주면 된다. - 그래프의 깊이를 구해야되는 문제이므로 DFS를 사용했으나, 계속해서 예제 입력 2를 통과하지 못하여 애를 먹었다. 결국 문제 이해력이 부족하여 시간을 많이 잡아 먹은 것 같다.
예제 입력 2
5 5 0 1 1 2 2 3 3 0 1 4
- 이 예제의 경우 친구 관계를 만족하므로 1이 출력되어야 한다. 하지만 나는
depth가 3으로 나와 계속해서 0이 출력되었다. 일단 그래프에서0 → 1 → 2 → 3노드까지 깊이 우선 탐색을 마치면 booleanvisited배열 상태는 4번 노드를 제외하고 모두 true로 설정이 되어 있을 것이다. - 여기서 3번까지 탐색을 마치면 1번 노드의 방문 상태는
true값이므로 현재 노드와 인접한 노드 중 방문하지 않은 노드가 존재하지 않으므로 재귀 호출은 그대로 끝나게 된다. 그래서depth가 3까지 밖에 찾지 못하는 것이다. - 하지만 2번 예제의 경우 마지막 4번 노드가 1번 노드와 연결되어 있으므로 이 문제에서 정의한 친구 관계를 만족한다고 가정하는 것 같다.. 방문을 마친 노드의 상태를 다시
visited[v] = false로 바꿔주고 재귀를 이어나가야 한다. - 즉, 문제에서 정의한 친구 관계의 조건을 찾으려면 존재하는 모든 노드와 연결된 노드의 depth가 4이어야 한다.
- 여기서 또 다른 문제가 발생하는데, 바로 시간 초과이다.. 😓
수정 전
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
A = new ArrayList[N];
visited = new boolean[N];
answer = 0;
for (int i = 0; i < N; i++) {
A[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());
A[a].add(b);
A[b].add(a);
}
for (int i = 0; i < N; i++) {
DFS(i, 0);
}
System.out.println(answer);
}
private static void DFS(int v, int depth) {
// depth가 4이면 탐색 종료
if (depth >= 4) {
answer = 1;
return;
}
if (visited[v]) {
return;
}
visited[v] = true;
for (int i : A[v]) {
if (!visited[i]) {
DFS(i, depth + 1);
}
}
visited[v] = false; // 방문 상태를 다시 false로 설정
}
}- 노드의 연결 부분만 다루는 인접 리스트도 사용 했고,
depth값이 4가 되면 바로 DFS 재귀 호출을 멈추도록 했는데 어디서 시간 초과가 나는지 찾을 수가 없었다. - 그러다가 문득, 위에서 예제 2번 입력값을 만족하기 위해
visited[v] = false설정한 부분이 떠올랐다. - 여기서 방문 상태를 false로 하는 순간, 많은 노드를 순환하기 때문에 시간 초과가 나는 것이 아닐까 생각했다. 즉, 재귀 호출을 적절하게 탈출할 수 있는 조건을 설정해야 했다.
수정 후 최종 코드
public class boj_13023 {
static ArrayList<Integer>[] A;
static boolean visited[];
static boolean check;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
A = new ArrayList[N];
visited = new boolean[N];
check = false;
for (int i = 0; i < N; i++) {
A[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());
A[a].add(b);
A[b].add(a);
}
for (int i = 0; i < N; i++) {
DFS(i, 0);
// 수정 부분
// 깊이가 4를 만족하는 경우 재귀 호출을 멈춘다.
if(check) {
break;
}
}
if (check) {
System.out.println(1);
} else {
System.out.println(0);
}
br.close();
}
private static void DFS(int v, int depth) {
if (depth == 4) {
check = true;
return;
}
if (visited[v]) {
return;
}
visited[v] = true;
for (int i : A[v]) {
if (!visited[i]) {
DFS(i, depth + 1);
}
}
visited[v] = false;
}
}
Backend Developer 💻 😺