[탐색] DFS(깊이 우선 탐색)

📌 DFS(Depth-First-Search)

⭐ 개념

• 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법
• 모든 경로를 방문해야 할 경우 사용에 적합
• Stack 구조
• 재귀함수로도 구현가능

✅ 시간복잡도

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)

⭐ 로직

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접노드를 다시 스택에 삽입하기
3. 스택 자료구조에 값이 없을때까지 반복

⭐ 코드

✅ Stack방식

static boolean[] visited = new boolean[9];
static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
static Stack<Integer> stack = new Stack<>();
public static void main(String[] args){
	// 출발점 1이므로 넣고 시작
	stack.push(1);
	visited[1] = true;
		
	while(!stack.isEmpty()) {
		int nodeIndex = stack.pop();
		for(int node : graph[nodeIndex]) {
			if(!visited[node]) {
				stack.push(node);
				visited[node] = true;
			}
		}
	}
}

✅ 재귀방식

static boolean[] visited = new boolean[9];
static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
public static void main(String[] args){	
	dfs(1);
}

static void dfs(int nodeIndex) {
	// 방문 처리
	visited[nodeIndex] = true;
	
	// 방문한 노드에 인접한 노드 찾기
	for (int node : graph[nodeIndex]) {
		// 인접한 노드가 방문한 적이 없다면 DFS 수행
		if(!visited[node]) {
			dfs(node);
		}
	}
}