TIL

어제는 BFS를 공부했으니 오늘은 DFS.

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS, Depth-First Search) 는 루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳 까지 내련간다. 더 이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 곳이 있으면 즉각 내려간다.

1에서 4까지 탐색하러 내려간다.
4에서 더이상 탐색할 곳이 없으니 3으로 올라간다.
5를 탐색 후 다시 2로 올라가서 6을 탐색.
그 후 1과 인접한 7과 8을 탐색.
8과 이어진 노드들을 탐색 후 탐색할 것이 없으면 다시 올라갔다 내려오길 반복한다.

백준 24479번: 알고리즘 수업- 깊이 우선 탐색 1

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로 탐색하면 된다.

1. 1~4까지 모두 이어져 있으므로 1->2->3->4의 순으로 탐색한다.
2. 5는 아무 간선과도 이어져있지 않으니 0을 출력한다.

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번을 해결할 수 있다.

https://www.acmicpc.net/problem/24480