[이것이 코딩테스트다] Chpter 05 DFS/BFS

탐색 - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

자료구조 - 데이터를 표현하고 관리하고 처리하기 위한 구조

삽입 : 데이터를 삽입한다

삭제 : 데이터를 삭제한다.

 

스택 - First IN Last Out

나중에 들어온 것이 먼저 빠짐. 샌드위치 구조

 

stack = []

stack.append(4)

stack.pop()

 

 

큐 - First In First Out

ex. 놀이공원 처음에 들어온 사람이 먼저 나감

 

queue = deque()

queue.append(5)

queue.popleft()

 

print(queue) -> 먼저 들어온 순서대로 출력

queue.reverse() -> 역순으로 바꾸기

 

재귀 함수

자기 자신을 다시 호출하는 함수

 

DFS

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 

그래프는 노드, 간선으로 표현되며 이때 노드를 정점이라고 말한다.

두 노드가 간선으로 연결되어 있다 == 두 노드는 인접하다

 

인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

INF = 999999

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

print(graph)

2차원 배열에 각 노드가 연결된 형태를 기록

대각선은 0,0,0 으로 채워짐

 

0번째 노드와 0번째 노드 사이는 0... 0번째 노드와 1번째 노드 사이는 7 ...

1번째 노드와 1번째 노드 사이는 0...

 

 

인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

# 행 (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)