찰떡개발자 코딩

이번에는 코딩테스트에 자주 출몰한다고하는..? DFS 알고리즘을 공부해 보려고한다.

비전공자로 시작한 만큼 하나하나 꾸준하게 나만의 공부를 하는것이 중요하다...!

시간날때마다 어떤것이든 하나씩 공부를 하는 습관을 길들이며...

DFS 깊이 우선 탐색 (Depth Fisrt Search)

"더 나아갈 길이 보이지 않을 때까지 깊이 들어간다"를 원칙으로 그래프 내의 정점을 방문하는 알고리즘

분기가 여러개가 있을때, 분기별로 끝까지 탐색해보고 이어진 다음 노드가 없을경우 다음분기로 넘어가는 방법이다.

완전 탐색 알고리즘에서 사용한다고 하는데, 자세하게 언제 어떻게 사용하는지는 알고리즘을 공부하고 난뒤 알아보도록 하자!

구현 방법 2가지

1). 순환 호출 이용(재귀)

2). 명시적인 스택 사용 - 인접한 정점들을 스택에 저장하였다가 다시 꺼내어 순회한다.

그래프 표현하기

정점의 개수, 간선의 개수, 탐색을 시작할 정점을 번호를 입력받으면서 시작한다.

이때

정점의 개수 : 우리가 방문해야 할 노드의 개수

간선의 개수 : 노드와 연결되어있는 간선의 개수

정점의 번호 : 첫번째 시작 노드의 번호

Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // 정점의 개수 
int m = sc.nextInt(); // 간선의 개수 
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 
int cnt =0;
boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열 

노드 방문 여부를 검사하기 위한 boolean 배열을 선언해 놓는다.

우선 인접리스트로 DFS를 구현해보자.

1. 인접 리스트로 구현

LinkedList에 정점과 간선을 넣어 인접 리스트를 만든다.

LinkedList<Integer>[] adjList = new LinkedList[n + 1];

for (int i = 0; i <= n; i++) {
	adjList[i] = new LinkedList<Integer>();
}

// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
// 입력으로 주어지는 간선은 양방향이다.
for (int i = 0; i < m; i++) {
	int v1 = sc.nextInt();
	int v2 = sc.nextInt();
	adjList[v1].add(v2);
	adjList[v2].add(v1);
}

for (int i = 1; i <= n; i++) { // 방문 순서를 위해 오름차순 정렬 
	Collections.sort(adjList[i]);
}

System.out.println("DFS - 인접리스트");
dfs_list(v, adjList, visited);

정점의 개수만큼 인접 리스트 배열을 만든다.

이때 LinkedList<Integer>[] <- LinkedList 배열로 선언한것을 주목하자!

여기에는 한 노드와 연결되어있는 간선들이 들어가게된다.

우리는 노드마다의 간선(양방향)을 입력하여 인접 리스트 배열을 만들게된다.

인접리스트를 다 만들고 나면, 순서대로 방문을 진행해야하기때문에 우선 sort를 진행한다.

1-1. 재귀를 이용해 DFS 구현

처음 DFS 함수를 호출하게 되면 int v에 탐색을 시작할 정점의 번호가 들어있고, 이 시작 정점부터 DFS 탐색을 시작한다.

dfs_list함수를 호출할때,

v = 탐색을 시작할 노드의 번호와,  adjList = 우리가 만든 인접리스트와 함께 주어진다.

정점을 방문하면 visited[v]에 true 값을 넣어 방문했다고 표시한 뒤 방문한 해당 정점을 출력

현재 정점과 인접한 정점들을 찾기위해 인접 리스트에 Iterator를 이용해 접근해 인접 정점을 탐색한다.

정점 v의 인접리스트를 순회하며 아직 방문하지 않은 visited가 false인 정점을 찾는다.

인접한 정점 w를 찾는다면 w에서부터 다시 DFS를 한다.

더 이상 방문하지 않은 정점이 없을 때까지 탐색을 한다.

// DFS - 인접리스트 - 재귀로 구현 
public static void dfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
	visited[v] = true; // 정점 방문 표시
    cnt++;
	System.out.print(v + " "); // 정점 출력
	System.out.print("회차 : "+cnt); //몇회차인지 출력
	Iterator<Integer> iter = adjList[v].listIterator(); // 정점 인접리스트 순회
	while (iter.hasNext()) {
		int w = iter.next();
		if (!visited[w]) // 방문하지 않은 정점이라면 
			dfs_list(w, adjList, visited); // 다시 DFS
	}
}

입력 : 

5 6 1
1 2
1 3
2 4
4 3
4 5
5 3

출력 : 

DFS - 인접리스트
1=> 방문
회차 : 1
2=> 방문
회차 : 2
4=> 방문
회차 : 3
3=> 방문
회차 : 4
5=> 방문
회차 : 5

인접리스트와 인접행렬로 구현했을때의 시간복잡도의 차이를 보자.

DFS 시간복잡도

정점의 수가 n이고, 간선의 수가 e인 그래프의 경우

인접 행렬로 구현한 그래프

1. 인접한 노드를 찾는 경우 : 인접 노드를 찾기 위해서는 한 행을 전부 읽어야하므로(모든정점을 순회) O(n)

2. 어떤 두 노드가 연결되어있는지 확인하는 경우 : 행렬을 통해 존재 여부를 바로 확인할 수 있으므로 O(1)

3. 그래프에 존재하는 모든 간선의 수 - O(n^2) (행렬을 전부 봐야하므로..?)

인접 리스트로 구현한 그래프

1. 인접한 노드를 찾는 경우 - 노드의 연결 리스트를 탐색하여야 하므로 O(v(노드의 연결리스트의 길이))

(최악의 경우에는 O(n)까지 걸릴 수 있겟네????)

2. 어떤 두 노드가 연결되어있는지 확인하는 경우 - 위와 마찬가지의 경우로 O(v(노드의 연결리스트의 길이))

(이것도 마찬가지로 최악의 경우에는 O(n)??)

3. 그래프에 존재하는 모든 간선의 수 - O(n+e) (노드 + 간선의 수만큼)

위와 같이 어떤 두 노드가 연결되어있는지를 확인하는 경우를 제외하면 인접 리스트로 그래프를 구현하여 DFS를 진행하는것이 효율적이다.

어떤 상황에서 어떤 알고리즘을 써야하는지 생각하고 사용해야 할 것이다....