DFS 되짚어보기 (Java)

🥰 DFS 개념

하나의 정점에서 시작해서 한 방향으로 더 이상 탐색할 수 없을 때까지 간 다음 다음 방향으로 탐색하는 것

재귀함수를 사용합니다.
또한, visited 배열을 선언하여 정점의 방문 여부를 관리합니다.
(방문 여부를 관리하지 않으면 Queue에 이미 들어갔던 정점이 또 들어가서 시간이 더 많이 걸릴 수 있습니다.)

기본적인 흐름은 다음과 같습니다.

1. 정점을 매개변수로 받는 함수를 하나 만듭니다.
2. 매개변수로 받은 정점을 탐색합니다.
3. for문을 사용해 해당 정점과 인접한 정점들을 확인하고 각 정점에 대해 다음 로직을 반복합니다.
   1) 해당 정점을 방문했는지 확인 후,
   2) 방문하지 않은 경우에만 해당 정점을 매개변수로 하는 함수를 호출합니다.(재귀)

🧐 코드

그래프가 위와 같다고 가정할 때,
노드 1부터 DFS를 시작하는 코드는 아래와 같습니다.

public class DfsTest {

	private static boolean visited[];
	private static int graph[][] = { {}, { 2, 3, 4 }, { 1, 4 }, { 1, 5 }, { 1, 2 }, { 3 } };

	public static void main(String[] args) {
		visited = new boolean[6];
		dfs(1);
	}

	private static void dfs(int nodeIdx) {
		visited[nodeIdx] = true;
		System.out.print(nodeIdx + " ");
		for (int node : graph[nodeIdx]) {
			if (!visited[node]) {
				dfs(node);
			}
		}
	}

}