👀 문제
https://www.acmicpc.net/problem/13023
👊 도전
1. 설계
- A->B->C->D->E와 같은 관계가 있는지 확인하기 위해 DFS를 이용한다.
- 친구관계를 이차원배열이 아닌 ArrayList를 이용하여 탐색 시간을 줄인다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int n, m;
static ArrayList<ArrayList<Integer>> list;
static boolean[] visit;
public static boolean dfs(int now, int depth) {
if(depth==5) return true;
visit[now]=true;
for(int i=0;i<list.get(now).size();i++) {//나와 연결된 사람들 체크
int next=list.get(now).get(i);
if(visit[next]) continue;
if(dfs(next, depth+1)) return true;
}
visit[now]=false;
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
list=new ArrayList<>();
for(int i=0;i<n;i++)
list.add(new ArrayList<Integer>());
for(int i=0;i<m;i++) {
int a=scan.nextInt();
int b=scan.nextInt();
list.get(a).add(b);
list.get(b).add(a);
}
for(int i=0;i<n;i++) {//시작점 체크
visit=new boolean[n];
if(dfs(i,1)) {
System.out.println("1");
return;
}
}
System.out.println("0");
}
}
3. 결과
🤟 성공 🤟
이차원 배열로 풀어서 계속 시간 초과가 발생했다. ArrayList를 사용하여 시간 문제를 해결하였다.
visit[false]를 처리해주지 않아 실패하였다.
4. 설명
- ArrayList를 이용한다
- 이차원배열을 이용할 경우 나와 연결되지 않은 곳(array[i][j]=0)도 체크해야하므로 시간 초과가 발생한다.
- 나와 연결된 곳들만 탐색하기 위해 ArrayList에 저장한다.
- n명의 관계를 저장하기 위해 ArrayList의 원소(ArrayList)를 n개 생성한 후, 각 사람마다 연결된 사람들 다시 Integer형으로 저장해준다.
- 각 사람마다 시작점을 주어 모든 경우의 수를 체크한다
- 시작점에 따라 ABCDE 관계를 찾을 수도 있고 아닐 수도 있기 때문에 main문에서 for문을 돌려 dfs를 호출하는 시작점을 모두 체크한다.
- DFS를 이용한다
- 나와 연결된 사람들을 타고타고 들어가야하므로 DFS를 이용한다.
- 특정 사람과의 연결을 체크한 적이 있는지 확인하기 위해 visit[]를 두어 방문 여부를 확인한다.
- 연결을 체크한 적이 있다면 continue로 패스한다.
- depth==5라면 ABCDE 관계를 찾은 것이므로 true를 리턴한다.
- now에 대한 사용이 끝났으므로 다음을 위해 visit[now]를 false 처리해줘야 한다.
👏 해결 완료!
참고
- 백준(BOJ) 13023 - ABCDE https://kyc0517.tistory.com/33