[Algorithm] 그래프 탐색 DFS(깊이 우선 탐색)에 대해서 with Java

과거에 나는 DFS와 BFS에 대해서 간단하게 정리한 경험이 있다. 이번에는 다시 한번 더 공부겸 좀 더 많은 것들을 기록하고자 다시 한번 더 포스팅을 해보자.

https://superohinsung.tistory.com/176

[DataStructure] 트리(Tree)

 

그래프 탐색(Graph Traversal)은 그래프의 모든 정점을 방문하는 과정이다.

 

DFS (Depth-First Search)란?

DFS는 한 정점에서 시작하여 가능한 한 깊이 내려간 후, 더 이상 갈 곳이 없으면 되돌아오는 방식으로 탐색하는 방법이다.
이 과정에서 방문한 정점들은 다시 방문하지 않도록 방문 체크(Visited Array) 를 사용한다.

DFS의 동작 방식:

1. 시작 노드를 방문하고 방문 표시
2. 해당 노드의 인접 노드를 재귀적으로 방문
3. 더 이상 방문할 노드가 없으면 백트래킹(되돌아감)

DFS는 재귀(Recursion) 또는 스택(Stack) 을 활용하여 구현할 수 있다.

 

DFS 구현 방식

DFS를 구현하는 방법은 인접 행렬(Adjacency Matrix) 방식과 인접 리스트(Adjacency List) 방식 두 가지가 있다.

방식	시간복잡도	특징
인접 행렬 (Adjacency Matrix)	O(V^2)	메모리 사용 많음 (V x V 크기 배열 필요)
인접 리스트 (Adjacency List)	O(V + E)	메모리 사용 적음 (필요한 연결 정보만 저장)

 

인접 리스트(Adjacency List)를 이용한 DFS 구현

주요 Point

• 각 정점의 연결 정보를 Node 객체로 관리
• 연결 리스트 형태로 저장하여 메모리를 절약
• 시간 복잡도: O(V + E) (정점과 간선 개수의 합)

public class AdjListSearch_DFS {

	private static class Node {
		public int vertex;  // 정점 번호
		public Node link;  // 연결된 정점 (리스트 형태)
		
		public Node(int vertex, Node link) {
			this.vertex = vertex;
			this.link = link;
		}
	}

	private static int V;  // 정점 개수
	private static int E;  // 간선 개수
	private static Node[] adjList;  // 인접 리스트

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();  // 정점 개수 입력
		E = sc.nextInt();  // 간선 개수 입력
		
		adjList = new Node[V];  // 인접 리스트 초기화 (null 상태)

		int from, to;
		for (int i = 0; i < E; i++) {
			from = sc.nextInt();
			to = sc.nextInt();
			
			// 무향 그래프 (양방향 간선 추가)
			adjList[from] = new Node(to, adjList[from]);
			adjList[to] = new Node(from, adjList[to]);
		}
		
		dfs(0, new boolean[V]);  // DFS 시작 (0번 정점부터 탐색)
	}

	// DFS 탐색 함수
	private static void dfs(int current, boolean[] visited) {
		visited[current] = true;  // 방문 체크
		System.out.print((char) (current + 65) + " ");  // 정점 출력 (A, B, C...)

		// 연결된 정점들을 순차적으로 방문
		for (Node temp = adjList[current]; temp != null; temp = temp.link) {
			if (!visited[temp.vertex]) {
				dfs(temp.vertex, visited);
			}
		}
	}
}

 

인접 행렬(Adjacency Matrix)를 이용한 DFS 구현

주요 Point

• 2차원 배열을 사용하여 정점 간 연결 정보를 저장
• 시간 복잡도: O(V^2) (모든 정점을 순회하며 확인해야 함)
• 작은 그래프에는 유리하지만, 큰 그래프에서는 메모리 사용이 많음

public class AdjMatrixSearch_DFS {

	private static int V;  // 정점 개수
	private static int E;  // 간선 개수
	private static int[][] adjMatrix;  // 인접 행렬

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		E = sc.nextInt();
		
		adjMatrix = new int[V][V];  // 초기화 (0으로 설정)

		int from, to;
		for (int i = 0; i < E; i++) {
			from = sc.nextInt();
			to = sc.nextInt();
			
			// 무향 그래프 (양방향 간선)
			adjMatrix[to][from] = adjMatrix[from][to] = 1;
		}

		dfs(0, new boolean[V]);  // DFS 시작
	}

	// DFS 탐색 함수
	private static void dfs(int current, boolean[] visited) {
		visited[current] = true;  // 방문 체크
		System.out.print((char) (current + 65) + " ");  // 정점 출력

		// 모든 정점 탐색하여 인접 여부 확인
		for (int i = 0; i < V; i++) {
			if (adjMatrix[current][i] != 0 && !visited[i]) {
				dfs(i, visited);
			}
		}
	}
}

 

 

예제 입력 및 실행 과정(공통)

입력

6 7
0 1
0 2
1 3
1 4
2 4
3 5
4 5

 

그래프 구조

    (0)
   /   \
 (1)   (2)
  | \   |
 (3) (4)
  |   |
 (5)---

 

DFS(0) → A → B → D → F → E → C

A B D F E C

 

시간 복잡도 비교

방식	시간 복잡도	메모리 사용량	특징
인접 행렬	O(V^2)	높음 (V x V 크기의 배열 필요)	빠르게 인접 여부 확인 가능
인접 리스트	O(V + E)	낮음 (E개 만큼의 연결 리스트)	메모리 절약 가능

• V(정점 수)가 작고, 밀집 그래프(Edge가 많음) → 인접 행렬 사용
• V(정점 수)가 크고, 희소 그래프(Edge가 적음) → 인접 리스트 사용

 

최적화 방법

1. DFS를 Stack 기반으로 구현하여 재귀 깊이 제한 해결 -> Stack은 Java에서 ArrayDeque를 사용
2. 방문 여부를 빠르게 확인하기 위해 boolean[] 사용
3. 양방향 간선의 경우 중복 탐색 방지
4. 희소 그래프에서는 인접 리스트 사용