문제
시간 제한 2초
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
8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7
예제 출력 1
1
문제 풀이
문제를 보니 저번에 풀었던 열결 요소의 개수 구하는 문제와 비슷한것 같다.
N의 최댓값은 2000 으로 작은 값을 가지고 있기 때문에 시간복잡도를 많이 고려할 필요는 없다고 생각한다.
다만 고려해볼 것은 DFS 탐색을 하는 도중 방문한 배열을 체크하는 것이다. DFS 탐색을 모두 끝냈을 때 원하는 값이 아닐 경우에는 그 방문 배열을 다시 false 형태로 둬야 하는 것인데 우선 문제를 보면서 설명해보겠다.
N = 8, M = 8 로 입력 받은 생태라고 가정하면
인접리스트와 방문 배열을 N의 길이만큼 초기화 시켜준다. 그리고 M번 만큼 입력된 수들을 인접리스트에 저장한다. 이때는 양 쪽에 모두 값을 저장해야 한다. 예를 들어 1 7 인 경우에는 index 1에 7 index 7 에도 1을 넣어줘야 한다.
그리고 여기서 arrive 라는 도착을 확인하는 변수를 초기화 시켜주고
DFS 를 수행해보겠다.
시작 노드를 0부터 시작하고 현재 깊이는 1인 상태인 DFS(0, 1) 재귀함수를 호출한다. 0은 이제 방문한 상태이니 방문 배열에 index 0 번째를 true 로 체크해준다.
0 과 이어져 있는 노드는 4이고 4는 방문하지 않은 상태이기 때문에 DFS(4, 2) 로 재귀함수를 호출하고 방문 배열도 index 4번째는 true 로 체크해준다.
0, 3, 6, 7 중에서 0은 방문했던 곳이기 때문에 제외 시켜준다.
3은 방문하지 않은 곳이기 때문에 DFS(3, 3)로 재귀함수를 호출하고 방문 배열도 index 3번째는 true 로 체크해준다.
4, 5, 7 중에서 4는 방문했던 곳이기 때문에 제외 시켜준다.
5는 방문하지 않은 곳이기 때문에 DFS(5, 4)로 재귀함수를 호출하고 방문 배열도 index 5번째는 true로 체크해준다.
3은 방문했던 곳이기 때문에 제외시켜준다. 이 때 더 이상 방문할 곳이 없기 때문에 호출했던 곳으로 돌아간다.
7은 방문하지 않은 곳이기 때문에 DFS(7, 4)로 재귀함수를 호출하고 방문 배열도 index 7번째는 true 로 체크해준다.
1 2 3 4 중에는 1은 방문하지 않은 곳이기 때문에 DFS(5, 5)로 재귀함수를 호출하고 방문 배열도 index 1 번째는 true로 체크해준다.
그런데 여기서 1 2 3 4 를 모두 돌아도 원하는 값이 만약 안나온다고 가정하면 여기까지의 상태는 7은 이미 방문한 상태이다. 그럼 다시 호출한 함수로 돌아가기 전 index 7 번째는 false 로 바꿔줘야 한다는 것을 기억해야 한다. (다음 index 에서 방문할 때는 방문한 상태가 아니기 때문이라서)
0 -> 4 -> 3 -> 7 -> 1 이 상태로 하나라도 존재하기 때문에 1을 출력하면 된다.
이를 코드에 적용시켜보겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class ABCDE {
private static ArrayList<Integer>[] A;
private static boolean[] visited;
private static boolean arrive;
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];
arrive = 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, 1);
if(arrive) {
break;
}
}
if(arrive) {
System.out.println(1);
}else {
System.out.println(0);
}
}
private static void DFS(int now, int depth) {
if(depth == 5 || arrive){
arrive = true;
return;
}
visited[now] = true;
for(int i : A[now]) {
if(!visited[i]) {
DFS(i, depth + 1);
}
}
visited[now] = false;
}
}
회고
언제부턴가 문제를 푸는 느낌보다는 책 내용을 정리하는 그런 모습이 보이기 시작한다...
아직 DFS 가 익숙치 않은 것도 있지만 혼자서 풀려고 하니 문제를 푸는 방법을 도출하기가 너무 힘들다. 이번 문제도 저번에 풀었던 내용을 계속 보면서 어찌저찌 풀어보았지만 아직은 혼자서 하기에는 부족한것 같다.
