[알고리즘] 그래프 이론 기초
2023. 8. 29. 12:57ㆍAlgorithm/with C++
0. 강의 2주차 이론
[알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회
이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord...
blog.naver.com
큰돌 선생님의 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inorder, postorder에 대한 블로그 포스팅.
이 글은 위에 내용을 다시 공부하기 싫어서 정리한 글입니다.
[출처] [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회|작성자 큰돌
1. 그래프
가. 정점과 간선
- 그래프 : 정점과 간선들로 이루어진 집합.
- 정점(vertex)(V)
: 노드라고도 불리며 그래프를 형성하는 기본 단위. - 간선(Edge)(E)
: 정점을 잇는 선. 양반향 간선, 단방향 간선이 있음.
나. indegree, outdegree
- indegree : 정점으로 들어오는 간선
- outdegree : 정점에서 나가는 간선
나. 가중치
- 가중치 : 정점과 정점 사이에 드는 비용.
2. 트리
가. 트리
- 트리
: 자식 노드와 부모 노드로 이루어진 계층적인 구조.
: 무방향 그래프.
: 사이클이 없는 자료구조.
V - 1 = E: 간선 수 = 노드 수 - 1
- 루트노드
: 가장 위에 있는 노드 - 내부노드
: 루트노드와 리프노드 사이에 있는 노드 - 리프노드
: 자식노드가 없는 노드
- 깊이 : 루트 노드에서 특정 노드까지 최단거리로 갔을 때의 거리.
- 높이 : 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리.
- 레벨
: 1번 노드를 0 레벨이라고 가정 → 2, 3번 노드는 레벨 1.
: 1번 노드를 1 레벨이라고 가정 → 2, 3번 노드는 레벨 2. - 서브트리
: 트리 내 하위 트리. - 숲(forest) : 트리로 이루어진 집합.
나. 이진트리(BT, Binary Tree)
다. 이진탐색트리(BST, Binary Search Tree)
- 이진 탐색 트리
: 이진트리의 일종.
: 노드의 오른쪽 하위 트리에는 "노드의 값보다 큰 값"이 있는 노드만 포함하고 왼쪽 하위트리에는 "노드의 값보다 작은 값" 위치.
: 검색에 용이.
1) 이진탐색트리의 시간복잡도
- 균형 잡힌 분포 : 탐색, 삽입, 삭제, 수정 모두 O(logN).
- 불균형한 분포 (선형적 구조) : O(N).
이진탐색트리는 삽입순서에 따라 영향을 받는다.
- AVL트리, 레드블랙트리
: 삽입순서에 상관없이 일정하게 균형 잡힌 이진탐색트리를 만드는 방법.
: map이 레드블랙트리로 구현되어 삽입, 탐색, 삭제, 수정이 일정한 시간복잡도 O(logN)을 보장함.
3. 인접행렬, 인접리스트
컴퓨터가 그래프를 인식하는 표현방법으로 인접행렬과 인접리스트가 있음.
가. 인접행렬
- 인접행렬
: 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬.
: 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐.
: 0은 두 정점 사이의 경로가 없음을 의미하며 1은 두 정점 사이의 경로가 있음을 의미.
인접행렬을 기반으로 탐색하기.
#include<bits/stdc++.h>
using namespace std;
const int V = 10;
bool a[V][V], visited[V];
void go(int from){
visited[from] = 1;
cout << from << '\n';
for(int i = 0; i < V; i++){
if(visited[i]) continue;
if(a[from][i])
go(i);
}
return;
}
int main(){
a[1][2] = 1; a[1][3] = 1; a[3][4] = 1;
a[2][1] = 1; a[3][1] = 1; a[4][3] = 1;
for(int i = 0;i < V; i++)
for(int j = 0; j < V; j++)
if(a[i][j] && visited[i] == 0)
go(i);
} a[1][2] = 1; a[1][3] = 1; a[3][4] = 1;
a[2][1] = 1; a[3][1] = 1; a[4][3] = 1;1 - 2, 1 - 3, 3 - 4은 연결되어 있다.
void go(int from){...}: 0번부터 방문 안 한 노드를 찾고 해당 노드부터 방문, 연결된 노드를 이어서 방문해서 출력하는 재귀함수.if(a[i][j] && visited[i] == 0): 한번 방문한 정점은 다시 방문하지 않게 만듦.
나. 인접리스트
- 인접 리스트(adjacency list)(adj)
: 그래프에서 정점과 간선의 관계를 나타내는 연결리스트.
#include<bits/stdc++.h>
using namespace std;
const int V = 4;
vector<int> adj[V];
int main(){
adj[0].push_back(1);
adj[0].push_back(2);
adj[0].push_back(3);
adj[1].push_back(0);
adj[1].push_back(2);
adj[2].push_back(0);
adj[2].push_back(1);
adj[3].push_back(0);
for(int i = 0; i < 4; i++){
cout << i << " :: ";
for(int there : adj[i]){
cout << there << " ";
}
cout << '\n';
}
// 이렇게도 할 수 있다.
for(int i = 0; i < 4; i++){
cout << i << " :: ";
for(int j = 0; j < adj[i].size(); j++){
cout << adj[i][j] << " ";
}
cout << '\n';
}
}
/*
0 :: 1 2 3
1 :: 0 2
2 :: 0 1
3 :: 0
*/인접리스트인 list로 구현해도 되고 vector로 구현해도 됨.
// vector
vector<int> adj[1004];
// list
list<int> adj[1004];
인접리스트를 구현에는 마지막 요소에 삽입과 해당 배열을 탐색하는 연산을 많이 사용한다.
#include<bits/stdc++.h>
using namespace std;
const int V = 10;
vector<int> adj[V];
int visited[V];
void go(int idx){
cout << idx << '\n';
visited[idx] = 1;
for(int there : adj[idx]){
if(visited[there]) continue;
go(there);
}
return;
}
int main(){
adj[1].push_back(2);
adj[2].push_back(1);
adj[1].push_back(3);
adj[3].push_back(1);
adj[3].push_back(4);
adj[4].push_back(3);
for(int i = 0; i < V; i++){
if(adj[i].size() && visited[i] == 0) go(i);
}
}
/*
1
2
3
4
*/const int V = 10;: 정점은 0번부터 9번까지 10개의 노드가 있다.
if(adj[i].size() && visited[i] == 0) go(i);: 연결된 남은 노드가 있다면 해당 노드를 방문했는지 확인한다.
다. 인접행렬과 인접리스트의 차이
- V는 정점(vertex)의 수
- E는 간선(edge)의 수
1) 공간복잡도
// 인접행렬
bool adj[V][V];
// 인접리스트
vector<int> adj[V];2) 시간복잡도
// 인접행렬
for(int i = 0;i < V; i++){
for(int j = 0; j < V; j++){
if(a[i][j]){
}
}
}
// 인접리스트
for(int j = 0; j < adj[i].size(); j++){
cout << adj[i][j] << " ";
}
3) 결론
그래프가 희소할 때는 인접리스트, 조밀할 때는 인접행렬이 좋다.
그래프가 희소할 때 (sparse)할 때는 인접행렬은 메모리 낭비가 큼.
그래프가 조밀할 때 (dense)할 때는 인접행렬이 인접 리스트보다 더 좋음. (속도가 빠름)
보통은 인접리스트를 쓰면 됨.
문제에서 sparse한 그래프가 많이 나옴.
단, 인접행렬로 주어진다면 그대로 인접행렬로 푸는 것이 좋다.
4. 맵과 방향벡터
상하좌우 4가지 방향으로 탐색한다면 위쪽부터 시계방향으로 탐색한다고 가정하면 y, x에 -1, 0 / 0, 1 / 1, 0 / 0, -1 을 더해가며 탐색한다.
x, y 가 아닌 y, x를 사용하는 이유는 2차원 배열은 y축으로 캐싱되기 때문이다.
(a[i][0]에 접근하면 a[i]를 캐싱함.)
#include<bits/stdc++.h>
using namespace std;
const int n = 3;
int a[n][n], visited[n][n];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
void go(int y, int x){
visited[y][x] = 1;
cout << y << " : " << x << "\n";
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if(a[ny][nx] == 0) continue;
if(visited[ny][nx]) continue;
go(ny, nx);
}
return;
}
int main(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> a[i][j];
}
}
go(0, 0);
}
/*
1 0 1
1 0 1
0 1 1
*/dx, dy: 방향벡터direction_y,direction_x라는 의미.if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
: 맵의 주어진 범위를 벗어나지 않게 하는 코드. 언더플로우와 오버플로우 에러를 방지.
// 8방면 탐색
#include <bits/stdc++.h>
using namespace std;
const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int main(){
int y = 0, x = 0;
for(int i = 0; i < 8; i++){
int ny = y + dy[i];
int nx = x + dx[i];
cout << ny << " : " << nx << '\n';
}
return 0;
}for(int i = 0; i < 8; i++){: 대각선을 고려해서 8방으로 탐색한다.
5. 깊이우선탐색(DFS, Depth First Search)
- DFS
: 시작 노드부터 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않음.
: 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘.
DFS(u, adj)
u.visited = true
for each v ∈ adj[u]
if v.visited == false
DFS(v, adj)
#include<bits/stdc++.h>
using namespace std;
const int n = 6;
vector<int> adj[n];
int visited[n];
void dfs(int u){
visited[u] = 1;
cout << u << "\n";
for(int v : adj[u]){
if(visited[v] == 0){
dfs(v);
}
}
cout << u << "로부터 시작된 함수가 종료되었습니다.\n";
return;
}
int main(){
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[4].push_back(2);
adj[2].push_back(5);
dfs(1);
}
/*
1
2
4
4로부터 시작된 함수가 종료되었습니다.
5
5로부터 시작된 함수가 종료되었습니다.
2로부터 시작된 함수가 종료되었습니다.
3
3로부터 시작된 함수가 종료되었습니다.
1로부터 시작된 함수가 종료되었습니다.
*/가. 구현방법 1 : 일단 검사
//재귀적인 호출 이전에 visited 검사.
void dfs(int here){
visited[here] = 1;
for(int there : adj[here]){
if(visited[there]) continue;
dfs(there);
}
}
//재귀적인 호출 이전에 visited 검사.
void dfs(int here){
for(int there : adj[here]){
if(visited[there]) continue;
visited[there] = 1;
dfs(there);
}
}다만 이럴 경우 시작지점에 대해 방문처리를 해주어야 합니다.
visited[1] = 1;
dfs(1);
나. 구현방법 2 : 일단 호출
void dfs(int here){
if(visited[here]) return;
visited[here] = 1;
for(int there : adj[here])
dfs(there);
}일단 dfs를 호출하고 해당 함수에서 visited를 검사해서 return 해 함수를 종료시키는 방법입니다.
다. 맵으로 주어진 경우
#include<bits/stdc++.h>
using namespace std;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int m, n, k, y, x, ret, ny, nx, t;
int a[104][104];
bool visited[104][104];
void dfs(int y, int x){
visited[y][x] = 1;
for(int i = 0; i < 4; i++){
ny = y + dy[i];
nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >=n || nx >= m) continue;
if(a[ny][nx] == 1 && !visited[ny][nx]){
dfs(ny, nx);
}
}
return;
}
int main(){
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(a[i][j] == 1 && !visited[i][j]){
ret++; dfs(i, j);
}
}
}
cout << ret << '\n';
return 0;
}
6. 너비우선탐색(BFS, Breadth First Search)
- BFS
: 시작 정점에서 다음 깊이의 정점으로 이동하기 전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘입니다.
: 같은 가중치를 가진 그래프에서 최단거리알고리즘으로 쓰입니다.
//**수도코드1 : 방문처리만 함.**
BFS(G, u)
u.visited = true
q.push(u);
while(q.size())
u = q.front()
q.pop()
for each v ∈ G.Adj[u]
if v.visited == false
v.visited = true
q.push(v)//**수도코드2 : 최단거리 알고리즘으로 사용.**
BFS(G, u)
u.visited = 1
q.push(u);
while(q.size())
u = q.front()
q.pop()
for each v ∈ G.Adj[u]
if v.visited == false
v.visited = u.visited + 1
q.push(v)차이점은 이 코드 한 줄이다.
v.visited = u.visited + 1
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[100];
int visited[100];
int nodeList[] = {10, 12, 14, 16, 18, 20, 22, 24};
void bfs(int here){
queue<int> q;
visited[here] = 1;
q.push(here);
while(q.size()){
int here = q.front(); q.pop();
for(int there : adj[here]){
if(visited[there]) continue;
visited[there] = visited[here] + 1;
q.push(there);
}
}
}
int main(){
adj[10].push_back(12);
adj[10].push_back(14);
adj[10].push_back(16);
adj[12].push_back(18);
adj[12].push_back(20);
adj[20].push_back(22);
adj[20].push_back(24);
bfs(10);
for(int i : nodeList){
cout << i << " : " << visited[i] << '\n';
}
cout << "10번으로부터 24번까지 최단거리는 : " << visited[24] - 1 << '\n';
return 0;
}
/*
10 : 1
12 : 2
14 : 2
16 : 2
18 : 3
20 : 3
22 : 4
24 : 4
10번으로부터 24번까지 최단거리는 : 3
*/- 만약 시작지점이 다수라면 처음 큐에 푸시하는 지점도 다수가 되어야 하며 해당 지점들의
visited를 모두1로 만들면서 시작해야 합니다. - 가중치가 다른 그래프 내에서 최단거리 알고리즘은 다익스트라, 벨만포드 등을 사용.
가. 맵으로 주어진 경우
#include <iostream>
#include <queue>
#include <utility> // for pair
#include <tuple> //for tie
using namespace std;
const int max_n = 104;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int n, m, a[max_n][max_n], visited[max_n][max_n], y, x, sy, sx, ey, ex;
int main(){
scanf("%d %d", &n, &m);
cin >> sy >> sx;
cin >> ey >> ex;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
}
}
queue<pair<int, int>> q;
visited[sy][sx] = 1;
q.push({sy, sx});
while(q.size()){
tie(y, x) = q.front(); q.pop();
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 0) continue;
if(visited[ny][nx]) continue;
visited[ny][nx] = visited[y][x] + 1;
q.push({ny, nx});
}
}
printf("%d\n", visited[ey][ex]);
// 최단거리 디버깅
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cout << visited[i][j] << ' ';
}
cout << '\n';
}
return 0;
}sy, sx: 시작 정점의 y, x 좌표.ey, ex: 도착 정점의 y, x 좌표.
7. DFS와 BFS비교
기본적으로 둘 다 시간복잡도는 인접리스트로 이루어졌다면 O(V + E)이고 인접행렬의 경우 O(V^2)가 되는 것은 동일함.
8. 트리순회
- 트리 순회(Tree traversal)
: 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정
: 노드를 방문하는 순서에 따라 후위순회, 전위순회, 중위순회, 레벨순회가 있음.
가. 후위순회
- 후위순회(postorder traversal)
: 자식 노드 → 자신 노드 순으로 방문.
postorder( node )
if (node.visited == false)
postorder( node->left )
postorder( node->right )
node.visited = true
나. 전위순회
- 전위순회(preorder traversal)
: 자신 노드 → 자식 노드 순으로 방문
: DFS
preorder( node )
if (node.visited == false)
node.visited = true
preorder( node->left )
preorder( node->right )
다. 중위순회
- 중위순회(inorder traversal)
: 왼쪽 노드 → 자신 노드 → 오른쪽 노드 순으로 방문
inorder( node )
if (node.visited == false)
inorder( node->left )
node.visited = true
inorder( node->right )
라. 레벨순회
- 레벨순회
: BFS
마. 구현 예시
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1004];
int visited[1004];
// 후위순회
void postOrder(int here){
if(visited[here] == 0){
if(adj[here].size() == 1)postOrder(adj[here][0]);
if(adj[here].size() == 2){
postOrder(adj[here][0]);
postOrder(adj[here][1]);
}
visited[here] = 1;
cout << here << ' ';
}
}
// 전위순회
void preOrder(int here){
if(visited[here] == 0){
visited[here] = 1;
cout << here << ' ';
if(adj[here].size() == 1)preOrder(adj[here][0]);
if(adj[here].size() == 2){
preOrder(adj[here][0]);
preOrder(adj[here][1]);
}
}
}
// 중위순회
void inOrder(int here){
if(visited[here] == 0){
if(adj[here].size() == 1){
inOrder(adj[here][0]);
visited[here] = 1;
cout << here << ' ';
}else if(adj[here].size() == 2){
inOrder(adj[here][0]);
visited[here] = 1;
cout << here << ' ';
inOrder(adj[here][1]);
}else{
visited[here] = 1;
cout << here << ' ';
}
}
}
int main(){
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
int root = 1;
cout << "\n 트리순회 : postOrder \n";
postOrder(root); memset(visited, 0, sizeof(visited));
cout << "\n 트리순회 : preOrder \n";
preOrder(root); memset(visited, 0, sizeof(visited));
cout << "\n 트리순회 : inOrder \n";
inOrder(root);
return 0;
}
/*
트리순회 : postOrder
4 5 2 3 1
트리순회 : preOrder
1 2 4 5 3
트리순회 : inOrder
4 2 5 1 3
*/
[출처] [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회|작성자 큰돌
'Algorithm > with C++' 카테고리의 다른 글
| [알고리즘] 1012번: 유기농 배추 (0) | 2023.08.31 |
|---|---|
| [알고리즘] 2178번: 미로 탐색 (+ 붙어있는 입력) (0) | 2023.08.30 |
| [알고리즘] 1859. 백만 장자 프로젝트 (0) | 2023.08.24 |
| [알고리즘] 4375번: 1 (0) | 2023.08.24 |
| [알고리즘] 1629번: 곱셈 (0) | 2023.08.12 |