GRAPH
📌 그래프
- 그래프는 인접하게 정점과 서로 이웃한 정점 간의 연결된 관계를 표현해 주는 비선형 자료구조
- 쉽게, 여러 개체들이 연결되어 있는 자료구조
💡 그래프 표현 방법
G = (V, E)
G = 그래프 (Graph) V = 정점 (Vertex) E = 간선 (Edge)
💡 그래프 종류
무방향 그래프 (V, E)
- 간선에 방향성이 없는 그래프로 정점 간의 순서가 없다.
- 즉, (A, B)와 (B, A)는 동일한 간선이다.
방향 그래프 <V, E>
- 간선에 방향이 있는 그래프로 정점에서 어디로 가는지의 방향과 순서를 표현할 수 있다.
- 즉, <A, B>와 <B, A>는 다른 간선이다.
여기서 잠깐!
비선형 자료구조눈 순서가 정해져 있지 않은 자료 구조이다.
근데 방향 그래프는 비선형 자료구조이면서 정점의 방향 순서를 알려주는 자료구조이다.
그렇다면 그래프는 선형 자료구조이지 않는가?
📌 방향 그래프는 순서가 있는 것 아닌가?
방향 그래프(Directed Graph)는 특정 정점 간의 방향성이 존재할 뿐,그래프 전체가 하나의 선형 구조를 가지는 것은 아니다.
예를 들어, [A → B] [B → C] [C → A] 라는 그래프는 방향성이 있지만, 배열처럼 일렬로 정리된 구조가 아니므로 비선형 자료구조에 해당한다.
✅ 결론
그래프는 데이터 간의 연결 관계를 표현하는 비선형 자료구조 이다. 방향성이 있다고 해서 선형 자료구조가 되는 것이 아니라, "일부 정점 간에 방향성이 존재할 뿐" 그래프 전체는 여전히 비선형적이다.
📌 인접 행렬
- 인접 행렬은 각 노드의 모든 이웃에 대해 하나의 행을 갖는다.
- 각 행의 값은 1(True)와 0(False)로 구성되어 있다.
| A | B | C | D | E | |
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 | 1 |
| D | 0 | 0 | 1 | 0 | 1 |
| E | 0 | 1 | 1 | 1 | 0 |
# 인접 행렬
a,b,c,d,e = range(5)
graph_array = [[0,1,1,0,0], [1,0,0,0,1], [1,0,0,1,1], [0,0,1,0,1], [0,1,1,1,0]]
print(f'A와 B의 인접행렬 : {graph_array[a][b]}') // 1
print(f'A와 C의 인접행렬 : {graph_array[a][c]}') // 1
print(f'A와 D의 인접행렬 : {graph_array[a][d]}') // 0📌 그래프 순회 (= 그래프 탐색 알고리즘)
- 그래프, 트리와 같은 연결 구조에서는 모든 정점(노드)을 순차적으로 탐색할 수 있다.
- 하나의 노드로 시작해서 차례대로 모든 노드를 한 번씩 방문한다.
💡 깊이 우선 순회 DFS (Depth First Search)
🩶 규칙
1. 현재 노드의 인접 노드 중 방문하지 않은 노드를 방문한다.
2. 방문한 노드의 인접 노드 중 더 가야할 인접 노드가 존재하지 않으면 방문했던 경로를 되돌아간다.
3. 방문하지 않은 노드가 더 이상 존재하지 않는 경우, 종료한다.
⚒️ 구현 방법
- DFS는 한 놈만 끝까지 쫒은 유형이라 재귀함수가 가장 일반적이다.
- 재귀를 타고, 타고, 타고, 타서 탈출 조건에 먼저 도달하고 그다음에 파라미터를 하나씩 바꿔가면서 정답을 찾는 방식
💡 너비 우선 순회 BFS (Breadth First Search)
🩶 규칙
1. 현재 노드의 인접 노드를 모두 방문한다.
2. 인접 노드 중 더 가야할 인접 노드가 존재하지 않으면 방문했던 경로를 되돌아간다.
3. 방문하지 않은 노드가 더 이상 존재하지 않는 경우, 종료한다.
⚒️ 구현 방법
- 가장 먼저 넣었던 것을 꺼내서 연결된 점을 Queue에 넣는다.
- 해당 큐가 빌 때까지 반복한다.
📎 대표적 문제 유형
- 경로 탐색 유형 (최단 거리 및 시간)
- 네트워크 유형 (연결)
- 조합 유형 (모든 조합 만들기)
✅ 그렇다면 어떤 알고리즘을 사용해야할까?
DFS BFS 두개 다 탐색 알고리즘이기 때문에 본인 손에 익는 알고리즘으로 사용하면 된다.
하지만 DFS를 더 선호한다.
DFS를 선호하는 이유는 동작 검증이 쉽기 때문이다.
DFS는 어찌 됐든 하나의 조합을 완성해서 정답과 비교하고, 또 다른 조합을 만들어서 정답과 비교하는 식으로 동작하기 때문에 정답을 비교하는 시점에 내가 기대한 대로 조합이 잘 나왔는지를 확인하기 빠르고 쉽다.
그에 비해 BFS는 한번에 여러 조합들을 한 칸 한 칸 씩 만들다 보니, 조합이 완성되어서 정답과 비교하는 시점에 언제 어떻게 이렇게 만들어졌지? 어디서 부터 틀린거지?를 분석하기가 까다로워진다.
하지만 DFS에서 동작하는 한 놈이 오래 걸리면 시간이 초과되기 때문에 이럴때는 BFS를 사용해야 한다.
그래서
DFS는 수행 시간 관점에서 복불복
BFS는 초반에는 느려보이더라도, 하나의 정답만 찾고나면 나머지 경우의 수는 정답에서 제외한다는 점때문에 시간복잡도가 낮다라고 생각한다.