[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 05 DFS/BFS - 탐색알고리즘 DFS/BFS

탐색 알고리즘 DFS/BFS

 

1 _ DFS

1. DFS
   • Depth-First Search
   • 깊이 우선 탐색
   • 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

      

2. 인접 행렬(Adjacency Matrix)
   • 2차원 배열로 그래프의 연결 관계를 표현하는 방식
   • 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

 

3. 인접 행렬 방식 예제

INF = 999999999 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
gragh = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(gragh)


## 결과
## [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

 

4. 인접 리스트(Adjacency List)
   • 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
     
     
5. 인접 리스트 방식 예제

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]


# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))


# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))


# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))


print(graph)


## 결과
## [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

 

6. DFS 예제

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]


visited = [False] * 9

dfs(graph, 1, visited)


## 결과
## 1 2 7 6 8 3 4 5

 

 

2 _ BFS

1. BFS
   • Breadth First Search
   • 너비 우선 탐색
   • 가까운 노드부터 탐색하는 알고리즘
     
     
2. BFS 예제

from collections import deque


def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
        
        for i in graph[v]:
        	if inot visited[i]:
            	queue.append(i)
                visited[i] = True
                
                
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]


visited = [False] * 9

bfs(graph, 1, visited)


## 결과
## 1 2 3 8 7 4 5 6

 

---

 

위 내용은 저자 나동빈의 < 이것이 취업을 위한 코딩 테스트다 with 파이썬 > 을 읽고, 공부한 내용입니다.

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154

이것이 취업을 위한 코딩 테스트다 with 파이썬