1. 문제 설명
문제 설명이 조금 직관적이진 않은데, A는 친구의 친구를 흘러가서 E까지 친구가 된다. 즉 DFS로 했을 때, 깊이가 5까지 가는 관계가 있는지 찾는 문제이다.
2. 접근 방식
문제에 나와 있듯이, 임의의 시작 노드를 선정해서, 거기서부터 깊이가 5인 DFS 재귀가 성립하는 게 있으면 1, 모든 노드를 시작 노드로 두고 해도, 깊이가 5인 재귀가 성립하지 않으면 0을 출력하면 된다.
3. 코드 분석
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static ArrayList<Integer>[] lists;
static boolean [] isVisited;
static boolean isValid = false;
static StringBuilder sb = new StringBuilder();
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());
lists = new ArrayList[N];
isVisited = new boolean[N];
for (int i = 0; i < N; i++) {
lists[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
lists[start].add(end);
lists[end].add(start);
}
for (int i = 0; i < N; i++) {
isVisited[i] = true;
dfs(0,i);
isVisited[i] = false;
if(isValid) break;
}
if(!isValid) System.out.println(0);
else System.out.println(1);
}
public static void dfs(int depth, int vertex) {
if(depth == 4){
isValid = true;
return;
}
for (int i = 0; i < lists[vertex].size(); i++) {
int next = lists[vertex].get(i);
if(!isVisited[next]){
isVisited[next] = true;
dfs(depth+1, next);
if(isValid) return;
isVisited[next] = false;
}
}
}
}
4. 성장하기
시간 초과가 날 수 없는 문제에서 시간초과
혹은 틀렸습니다
가 났다.
DFS는 최악의 시간복잡도가 O(V+E)로 해당 문제에서는 정점이 최대 2000, 간선이 최대 2000이다. 최악의 경우, 해당 DFS를 모든 노드에 대해 실행해야하니, 4000*2000 = 8000000 이 된다.
근데 나는 2가지 실수를 해서 시간 초과가 났다.
- 기저 조건의 종료를
depth == 5
로 두었다. 그래서 깊이가 6인 것을 찾아야 그만뒀다. - 시작 노드를 방문처리하지 않았다.
내 풀이의 경우, 다음 Node 들어가기 전에, 해당 Node를 방문처리하는 형식으로 했다.
그러니까 현재 노드가 아닌, 다음 노드를 true 처리 한 것이다. 이런 식으로 하니, 맨 처음 시작 노드에 대한 방문처리를 빼먹었다.
public static void dfs(int depth, int now) {
if(depth == 4 || isValid == true){
isValid = true;
return;
}
isVisited[now] = true;
for (int i = 0; i < lists[now].size(); i++) {
int next = lists[now].get(i);
if(!isVisited[next]){
dfs(depth+1, next);
}
}
isVisited[now] = false;
}
이런 식으로 현 노드에 대해 처리를 해준다면, 시작 정점을 놓칠 일은 없을 것이다.
(이게 싫다면, DFS 함수 들어오기 전에, 시작 노드에 대한 방문처리를 해줘야 한다.)
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[백준] 1167 트리의 지름 java (0) | 2024.07.13 |
---|---|
[백준] 2178 미로탐색 java (0) | 2024.07.13 |
[백준] 신기한 소수 java (0) | 2024.07.11 |
[백준] 10989 수 정렬하기 3 (0) | 2024.07.07 |
[백준] 1517 버블소트 java 쉬운 풀이 (0) | 2024.07.06 |