[Python 기본] 탐색 알고리즘(DFS / BFS) 1

그래프

그래프란? 지도, 네트워크, 연결성 등 현실적인 현상들을 점/선으로 추상화하는 것을 말한다.

우리가 해야 할 일은 이렇게 추상화되어 있는 그래프들을 코드화하는 작업이다.

이는 두 가지 방식으로 구현할 수 있다.

 

그래프의 구현

1) 행렬(Matrix) 방식으로 구현

tip) 거리를 계산하게 될 때는 자기 자신으로 가는 값(0)과 연결이 없는 경우의 값(inf)을 구분해야 한다.

 

2) 인접 리스트 방식으로 구현

- 연결성만 바라보고 컴팩트하게 구성되었다.

- 행렬 표현 방식보다 직관성은 떨어진다.

 

예시

다음과 같은 그래프를 각각 행렬, 인접 리스트 방식으로 구현하고자 한다.

 

1) 행렬

	0	1	2
0	0	7	5
1	7	0	inf
2	5	inf	0

 

tip) inf를 표현하는 방법은

- 직접 입력하는 방법: inf = 9999999999999999999999999

- 파이썬의 무한대 인식 활용법: inf = float('inf')

 

[코드화]

inf = float('inf')

m = [
      [0,7,5],
      [7,0,inf],
      [5,inf,0]
]
m
# [[0, 7, 5], [7, 0, inf], [5, inf, 0]]

# 0번 도시에서 1번 도시가 연결되었나요?
m[0][1]
# 7

# 2번 도시에서 1번 도시가 연결되었나요?
m[2][1]
# inf

 

2) 리스트

0 : [(1,7), (2,5)]

1 : [(0,7)]

2 : [(0,5)]

 

[코드화]

리스트 구현

g_1 = [
    [(1,7),(2,5)], # 0번 도시의 연결 리스트업
    [(0,7)],       # 1번 도시의 연결 리스트업
    [(0,5)]        # 2번 도시의 연결 리스트업
]
g_1
# [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

# 0번 도시에서 1번 도시가 연결되었나요?
g_1[0][0][1]
# 7

 

딕셔너리 구현

g_dict = {
    '0':[(1,7),(2,5)],
    '1':[(0,7)],
    '2':[(0,5)]    
}
g_dict
# {'0': [(1, 7), (2, 5)], '1': [(0, 7)], '2': [(0, 5)]}

# 0번 도시에서 1번 도시가 연결되었나요?
g_dict['0'][0][1]
# 7

 

tip) 인접 리스트 방식을 리스트 자료형으로 코드화할 때, 0번 도시가 없는 경우

: 가상의 0번 도시를 만들어서 도시 번호와 인덱스를 일치시키면 편리하다.

g_2 = [
    [], # -> 가상의 0번 도시 세팅
    [(2,7),(3,5)], # 1번 도시의 연결 리스트업
    [(1,7)],       # 2번 도시의 연결 리스트업
    [(1,5)]        # 3번 도시의 연결 리스트업
]
g_2
# [[], [(2, 7), (3, 5)], [(1, 7)], [(1, 5)]]

 

 

그래프 탐색이란?

엣지를 따라 모든 노드를 방문하는 것을 뜻한다. 대표적인 방법으로 BFS와 DFS가 있다.

- BFS(Breadth First Search)와 DFS(Depth First Search)의 차이

 

DFS(Depth First Search)

- 깊은 부분을 우선적으로 탐색(계속해서 파고 들어간다)

- Stack을 통해 구현(FILO)

 

0) '가야할 노드의 목록'과 '방문한 노드의 목록'이라는 두 가지 기록지(스택)를 만든다.

 

1) 탐색을 시작할 노드 '1'을 두 가지 목록에 저장한다.

가야할 노드의 목록	방문한 노드의 목록
1	1

 

2) 현재 위치인 노드 '1'에 연결된 '8', '3', '2'번 노드를 '가야할 노드의 목록'에 집어넣는다.

 

가야할 노드의 목록	방문한 노드의 목록
1	1
8
3
2

 

3) Stack을 통해 가야할 노드의 목록 맨 마지막에 위치한 노드 '2'를 방문하고 방문 처리한다.

가야할 노드의 목록	방문한 노드의 목록
1	1
8	2
3
2

 

4) 현재 위치인 노드 '2'에 연결된 '7', '1'번 노드를 '가야할 노드의 목록'에 추가한다.

가야할 노드의 목록	방문한 노드의 목록
1	1
8	2
3
2
7
1

 

5) 이미 방문한 맨 마지막의 노드 '1'은 패스하고, 그 다음으로 위치한 '7'을 방문하고 방문 처리한다.

가야할 노드의 목록	방문한 노드의 목록
1	1
8	2
3	7
2
7
1(pass)

 

6) 앞선 과정을 '가야할 노드의 목록'의 노드들이 모두 사라질 때 까지 반복한다.

가야할 노드의 목록	방문한 노드의 목록
1	1
8	2
3	7
2	6
7	8
1(pass)	3
8	4
6	5
2(pass)
7(pass)
5
4
1(pass)
5
3(pass)

 

최종 결과: 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

(2번째 방문 노드에 따라 결과가 조금 다를 수 있음)

 

BFS(Breadth First Search)

- 가까운 부분을 우선적으로 탐색(일단 수평적으로 탐색한다)

- Queue를 통해 구현(FIFO)

 

0) '가야할 노드의 목록'과 '방문한 노드의 목록'이라는 두 가지 기록지(스택)를 만든다.

 

1) 탐색을 시작할 노드 '1'을 두 가지 목록에 저장한다.

가야할 노드의 목록	방문한 노드의 목록
1	1

 

2) 현재 위치인 노드 '1'에 연결된 '8', '3', '2'번 노드를 '가야할 노드의 목록'에 집어넣는다.

가야할 노드의 목록	방문한 노드의 목록
1	1
8
3
2

 

3) Queue를 통해 가야할 노드의 목록 맨 처음에 위치한 노드 '8'을 방문하고 방문 처리한다.

가야할 노드의 목록	방문한 노드의 목록
1	1
8	8
3
2

 

4) 현재 위치인 노드 '8'에 연결된 '7', '1'번 노드를 '가야할 노드의 목록'에 추가한다.

가야할 노드의 목록	방문한 노드의 목록
1	1
8	8
3
2
7
1

 

5) '가야할 노드의 목록'의 맨 첫번째 노드 '3'을 방문하고 방문 처리한다.

가야할 노드의 목록	방문한 노드의 목록
1	1
8	8
3	3
2
7
1

 

6) 앞선 과정을 '가야할 노드의 목록'의 노드들이 모두 사라질 때 까지 반복한다.

가야할 노드의 목록	방문한 노드의 목록
1	1
8	8
3	3
2	2
7	7
1(pass)	5
5	4
4	6
1(pass)
7(pass)
1(pass)
8(pass)
6
2
4
3
5
3

 

최종 결과: 1 -> 8 -> 3 -> 2 -> 7 -> 5 -> 4 -> 6

(2번째 방문 노드에 따라 결과가 조금 다를 수 있음)

 

=> DFS와 BFS의 차이는 STACK을 쓰느냐 QUEUE를 쓰느냐의 차이이다.