어제는 BFS를 공부했으니 오늘은 DFS.
깊이 우선 탐색(DFS, Depth-First Search) 는 루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳 까지 내련간다. 더 이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 곳이 있으면 즉각 내려간다.
1에서 4까지 탐색하러 내려간다.
4에서 더이상 탐색할 곳이 없으니 3으로 올라간다.
5를 탐색 후 다시 2로 올라가서 6을 탐색.
그 후 1과 인접한 7과 8을 탐색.
8과 이어진 노드들을 탐색 후 탐색할 것이 없으면 다시 올라갔다 내려오길 반복한다.
https://www.acmicpc.net/problem/24479
입력이
5 5 1
1 4
1 2
2 3
2 4
3 4
다음과 같이 주어지면
정점의 갯수는 5, 간선의 갯수는 5, 시작 정점은 1이고
간선 5개는 각각 (1,4) (1,2) (2,3) (2,4) (3,4) 이다.
그러면 이러한 모양이 되는데
이걸 DFS로 탐색하면 된다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main{
static int[] visited;
static ArrayList<ArrayList<Integer>> graph;
static int N, M, R;
static int cnt = 1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 정점의 수
M = Integer.parseInt(st.nextToken()); // 간선의 수
R = Integer.parseInt(st.nextToken()); // 시작 정점
visited = new int[N + 1];
graph = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i <= N; i++) {
graph.add(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());
graph.get(a).add(b);
graph.get(b).add(a);
}
for (int i = 1; i <= N; i++) {
Collections.sort(graph.get(i));
//Collections.sort(graph.get(i),Collections.reverseOrder());
}
dfs(R);
for (int i = 1; i <= N; i++) {
bw.write(visited[i] + "\n");
}
bw.flush();
bw.close();
}
public static void dfs(int start) {
visited[start] = cnt;
for (int i = 0; i < graph.get(start).size(); i++) {
int temp = graph.get(start).get(i);
if (visited[temp] == 0) {
cnt++;
dfs(temp);
}
}
}
}
리스트안의 요소를 정렬할 때 reverseOrder를 하면 24480번을 해결할 수 있다.