https://www.acmicpc.net/problem/13023
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main{
static int n, m;
static ArrayList<ArrayList<Integer>> list;
static boolean[] visit;
static int answer = 0;
public static void dfs(int v, int cnt)
{
if(cnt == 5)
{
System.out.println(1);
System.exit(0);
return;
}
for(int nv : list.get(v)){
if(visit[nv]) continue;
visit[nv] = true;
dfs(nv, cnt+1);
visit[nv] = false;
}
}
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());
m = Integer.parseInt(st.nextToken());
list = new ArrayList<ArrayList<Integer>>();
visit = new boolean[n];
for(int i=0; i<n; i++){
list.add(new ArrayList<Integer>());
}
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.get(a).add(b);
list.get(b).add(a);
}
for(int i=0; i<n; i++){
visit[i] = true;
dfs(i, 1);
visit[i] = false;
}
System.out.println(answer);
}
}
처음엔 배열로 입력받아 시간초과가 났다. cnt == 5가 되었을 때 바로 System.exit(0)으로 종료를 해줘도 시간초과가 났다.
배열로 한다면 배열의 값인 노드를 찾기 위해 for문에서 0부터 n-1까지 모든 원소를 탐색해야 한다.
ArrayList로 할 경우 친구인 노드들만 add로 저장했으므로, 탐색해야하는 노드가 훨씬 줄어들어 시간이 적게 걸리게 된다.
이렇게 정점의 개수가 많아질 경우에는 ArrayList 를 사용하는게 효율적이다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 16929 - Two Dots (0) | 2022.12.18 |
---|---|
[JAVA] 백준 1182 - 부분수열의 합 (0) | 2022.12.17 |
[JAVA] 백준 7576번- 토마토 (0) | 2022.12.16 |
[JAVA] 백준 7562번- 나이트의 이동 (0) | 2022.12.16 |
[JAVA] 백준 2667번- 단지번호붙이기 (0) | 2022.12.16 |