그래프
그래프 G = (V, E)
이때 V는 노드, E는 에지이다. 에지 E는 V * V 의 부분집합이다 (즉 노드와 노드를 연결하는 모든 쌍의 부분집합)
유향그래프 vs 무향그래프 : 에지의 방향성에 따라
- 유향그래프 : (i, j) ≠ (j, i)
- 무향그래프 : (i, j) = (j, i) 양방향 유향그래프
가중그래프 G = (V, E, W)
- 가중그래프(weighted graph)는 에지마다 가중치 W를 가진다
보통 사람은 그래프를 손으로 그려 시각적으로 보는 걸 선호하지만, 컴퓨터로는 2차원 행렬 또는 리스트로 표현한다.
그래프의 탐색 자체는 그리 어렵지 않다. 효율적인 탐색을 위해 깊이우선, 너비우선 탐색으로 분류할 수 있다. 그리 어렵지 않은 내용이므로 그림은 과감히 생략ㅎ
깊이우선탐색 (Depth First Search)
깊이우선탐색은 연결된 노드를 따라 계속해 탐색하는 것으로, 더 이상 탐색할 노드가 없을 때까지 이어진 에지를 타고 깊게 들어간다. DFS는 최대한 한붓그리기로 붓이 끊어지지 않을 때까지 탐색한다.
- 시간복잡도 : 탐색 여부를 알아야 하므로 어쨌거나 모든 노드와 에지를 조사해야 한다 O(|V| + |E|)
- 공간복잡도 : 모든 노드에 방문 여부를 체크해야 하므로 O(|V|)
너비우선탐색 (Breadth First Search)
너비우선탐색은 한 노드에서 연결된 노드를 계속 탐색하는 것이다. DFS가 노드 하나하나를 깊이있게 파는거라면, BFS는 넓고 얕게 탐색한다. 이때 어떤 특정 노드에 연결된 노드를 차례대로 확인해야 하므로 FIFO(First In, First Out)의 큐(Queue)를 사용한다.
- 시간복잡도 : 모든 노드가 큐에 들어갔다 나와야 하고, 이는 연결된 에지를 모두 확인하는 과정이므로 O(|V| + |E|)
- 공간복잡도 : 모든 노드에 방문 여부를 확인하고, 큐에 들어가 있는지를 체크해야 하므로 O(|V|)
🧨 그래프 탐색 알고리즘, DFS와 BFS의 구현
- 문제 출처 : 백준 1260번
- 문제 난이도 : 실버2
- 문제 링크 : www.acmicpc.net/problem/1260
가중치가 없는 무향 그래프에서의 DFS, BFS를 구현했다. 역시나 교수님 코드를 참고해 작성했다.
깊이우선탐색은 재귀적으로 호출해 깊게 들어갈 수 있도록 했고, 너비우선탐색은 Queue를 이용해 같은 레벨의 노드를 차례대로 방문하도록 했다. 교수님은 그래프를 리스트로 구현하셨지만 C++로 옮기는 과정에서 탐탁치 않아 행렬로 바꿨다.
+ 백준 1260번은 아마 리스트로 구현하면 시간초과가 날 가능성이 높아서 2차원 행렬로 했다.
+ push_back 이나 기타 동적할당이 필요한 게 아니라면 int [] 배열을 쓰자.
+ 재작년 알고리즘 수업 들을 때 교수님이 왜 isinQueue가 또 하나 더 필요한건지 설명해주셨는데 까먹었다. 작년 수업을 들은 파릇파릇한 친구들의 기억을 믿어보겠다 ^^
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, v;
int isMarked[1001] = {false};
void recursiveDFS(int G[1001][1001], int start) {
if (isMarked[start]) return;
else {
isMarked[start] = true;
cout << start << ' ';
// no weight DFS (가중치 없는 노드와 연결된 노드만 입력받는 DFS)
for (int i = 1; i < n + 1; i++) {
if (G[start][i] && isMarked[i] == false)
recursiveDFS(G, i);
}
return;
}
}
void BFS(int G[1001][1001], int start) {
int isMarked[1001] = {false};
int isinQueue[1001] = {false};
queue<int> q;
q.push(start);
isinQueue[start] = true;
while(!q.empty()) {
int current = q.front();
q.pop(); //void
cout << current << ' ';
isMarked[current] = true;
for(int i = 1; i < n + 1; i++) {
if(!isMarked[i] && !isinQueue[i] && G[current][i]) {
q.push(i);
isinQueue[i] = true;
}
}
}
return;
}
int main() {
cin >> n >> m >> v;
int G[1001][1001] = {0};
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
G[x][y] = 1;
G[y][x] = 1;
}
recursiveDFS(G, v);
cout << '\n';
BFS(G, v);
return 0;
}
'Problem Solving > Algorithm, DS' 카테고리의 다른 글
[알고리즘] 최단거리 (다익스트라, 벨만포드, 플로이드와셜 알고리즘) Dijkstra, Bellman-Ford, Floyd-Warshall Algorithm (0) | 2021.02.06 |
---|---|
[알고리즘] 최소신장트리(MST)와 프림, 크루스칼 알고리즘 + 백준1197번 (0) | 2021.01.29 |
[알고리즘] Greedy Algorithm (탐욕알고리즘, 백준 문제모음) (0) | 2021.01.10 |
[알고리즘] 기수정렬, 계수정렬 Radix, Counting Sort (C++ 구현) (0) | 2021.01.04 |
[알고리즘] 힙 정렬 Heap Sort (C++ 구현, make_heap, pop_heap) (0) | 2021.01.03 |