[알고리즘 코테] DFS/BFS

DFS(Depth First Search) / BFS(Breadth First Search)

1) 방문 리스트 : 방문 처리 목적 / 정점의 개수만큼 길이 생성

visited = [0] * 정점의 개수

2) 인접 행렬 / 인접 리스트 : 노드, 간선 연결 저장

3) stack / queue : 실시간 현황

 

💡 자료구조 : 스택 (선입후출, FILO)

1. 루트 노드를 스택에 넣고 방문 처리 한다.
2. 스택 최상단 노드의 인접 노드 중 방문하지 않은 노드 하나를 스택에 넣고 방문 처리한다. 만약 인접 노드를 모두 방문한 경우 스택을 Pop 한다.
3. 2 단계를 더 이상 수행할 수 없을 때 까지 (스택이 빌 때 까지) 반복한다. 

💡 자료구조 : 큐 (선입선출, FIFO)

1. 루트 노드를 큐에 넣고 방문 처리한다.
2. 방문 처리한 노드를 큐에서 제거하고, 제거한 노드의 방문하지 않은 모든 인접 노드를 큐에 넣고 방문 처리한다.
3. 2 단계를 더 이상 수행할 수 없을 때 까지 (큐가 빌 때 까지) 반복한다.

Graph

• 두 노드가 간선으로 연결되어 있다 → ‘두 노드는 인접하다’
• 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것
• 프로그래밍에서 2가지 방식으로 그래프를 표현 : 인접 행렬, 인접 리스트

인접 행렬 / 인접 리스트

1. 인접 행렬 : 행렬로 정점들 사이의 관계를 표현하는 방식, 2차원 배열에 각 노드가 연결된 형태를 기록함.

연결되지 않은 값들은 무한의 비용으로 작성하기도 함.

2. 인접 리스트 : 각 정점에 연결된 노드들의 정보를 저장하는 방식,리스트로 각 노드의 연결된 형태를 기록함.

• 메모리 면에서는 인접 행렬이 모든 관계를 저장하므로 노드 개수가 많을수록 불필요하게 낭비하는 메모리가 많을 수 있으나, 속도의 경우 인접 리스트가 특정한 두 노드가 연결되어 있는지 하나씩 확인해야 하기에 속도가 느림.