[ALPS Study] 탐색 -그래프와 DFS(깊이 우선 탐색)(1)

탐색이란? 특정 공간을 모두 돌아보는 행위 ...

 - 깊이 우선 탐색(Depth FIrst Search) 

 - 너비 우선 탐색(Breadth First Search)

+ 트리에서의 순회

 

DFS(Depth First Search) :깊이 우선 탐색

 -> 특정 정점에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 모두 탐색하는 방식.

 

1. 미로에서 길을 잃었다. 미로에 대한 정보를 모를 때, 미로를 어떻게 해야 빠져나올 수 있을까? 

2. 친구들과 여행을 떠나기로 했다. 가고 싶은 장소를 모두 방문한다 할 때 경로를 어떻게 표현 할 것인가?

3. "그래프"가 주어졌을 때, 이를 어떤 식으로 코드에 이용할 수 있을까?

 

 

즉 쉽게 말해서 한 길을 따라 쭉 파고들고, 길의 끝을 만나면 다시 갈림길로 되돌아와 다른 갈림길로 또 쭉 파고들고 또 되돌아오고 ... 

위의 그래프를 깊이우선탐색을 통해 돌아보면 1-2-3-4-5-6-7 이 될 것! (이 때, 7번 노드의 경우는 코드 처리 필요, 하지 않으면 4번 노드에서 7번을 중복으로 탐색하는 실수를 할 수 있음)

 

 

그래프

 

* 그래프를 프로그래밍에 적용시키는 방법 : 배열(연결 정보 담음), 연결리스트

 

- Adjacency Matrix(인접 행렬)

  adj[i][j] := i에서 j로 연결된 간선의 수(이차원 배열)

 

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

참고로 위 그래프는 간선의 방향이 없는 그래프이다. 따라서 x와 y가 연결되어 있다면 y와 x도 연결되어 있다. 즉, 저 표를 보면 대각선을 기준으로 대칭의 형태를 띈다.

 

- Adjacency List(인접 리스트)

 adj[i][j] 의 원소 := i와 인접한 정점들(일차원 배열)

1| 2 4     2| 1 3 5 3| 2        4| 1 6 7 5| 2       6| 4 7    7| 4 6

* 정점의 개수가 max 일 때, 배열의 크기

 - Matrix : max * max

 - List : 간선의 수*2

--> 정점이 많아질 수록 이차원 배열의 메모리 사용량이 기하급수적으로 늘어남!