그래프는 정점과 정점들을 잇는 간선들의 집합으로 이루어진 자료구조입니다.
이 글에서는 그래프를 저장하는 방법과, 그래프를 탐색하는 방법에 대해 알아보도록 합시다.
다음과 같은 그래프를 저장한다고 생각해 봅시다.
정점은 총 6개 입니다. \(V = \{1,2,3,4,5,6\}\)
간선은 총 7개 입니다. \(E = \{(1,2),(2,3),(2,5),(2,6),(3,4),(3,6),(4,5)\}\)
일반적으로 그래프를 저장하는 방법에는 3가지가 있습니다.
1. 인접 행렬
$$\left[\begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0\end{matrix}\right]$$
\(|V| \times |V|\)크기의 2차원 배열을 만듭니다.
정점 \(u\), \(v\)를 잇는 간선 \((u,v)\)가 존재한다면 배열의 \(u\)행 \(v\)을 1로, 그렇지 않다면 0으로 설정하면 됩니다.
\(|V|^2\)의 메모리를 차지하기 때문에 일반적으로 정점의 개수가 \(10^4\)이상인 경우에는 사용할 수 없지만, 어떤 두 정점이 연결되었는지 \(O(1)\)에 알 수 있다는 장점이 있습니다.
2. 인접 리스트
$$\left[\begin{array}{r|rrr} 1 & 2 \\ 2 & 1 & 3 & 5 & 6 \\ 3 & 2 & 4 & 6 \\ 4 & 3 & 5 \\ 5 & 2 & 4 \\ 6 & 2 & 3 \end{array}\right]$$
\(|V|\)개의 동적 배열을 만듭니다.
각 정점 \(v\)에 대해, \(v\)에 연결된 다른 모든 정점들을 \(v\)번 인덱스의 동적 배열에 저장합니다.
\(|E|\)의 메모리를 차지하면서도, 어떤 정점 \(v\)와 이웃한 모든 정점을 살펴보는데 가장 유리한데, 이것은 일반적으로 그래프에 관련된 알고리즘에 많이 사용되는 작업 중에 하나입니다.
따라서 대부분의 경우에 그래프를 저장한다고 하면, 이 방식으로 그래프를 저장하게 됩니다.
3. 간선 리스트
$$\{(1,2),(2,3),(2,5),(2,6),(3,4),(3,6),(4,5)\}$$
단순히 모든 간선을 저장합니다. 일반적으로는 쓰이지 않지만, 간선의 정보만을 이용하는 몇몇 알고리즘에서 쓰입니다.
이제 그래프를 저장하는 방법을 알았으니, 그래프를 탐색하는 2가지 방법에 대해 알아보도록 합시다.
아까 썼던 그래프를 사용하도록 합시다!
1. DFS (Depth First Search)
DFS는 그래프를 '깊이 우선'으로 탐색해 나가는 알고리즘입니다.
각 정점에 도착하면, 아직 방문하지 않은 다른 정점들 중에 하나를 선택해 방문합니다.
만약 방문하지 않은 정점이 없다면, 이전 정점으로 퇴각하여 탐색을 계속 하게 됩니다.
1번 정점에서 시작해 이 그래프를 탐색한다고 생각해봅시다. 또, 방문하지 않은 정점들이 여러 개일 경우, 가장 정점 번호가 작은 것을 먼저 탐색한다고 합시다.
그러면 위의 그래프를 DFS탐색한 결과는 다음과 같습니다.
$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 4(퇴각) \rightarrow 3(퇴각) \rightarrow 6 \rightarrow 3(퇴각) \rightarrow 2(퇴각) \rightarrow 1(퇴각)$$
잘 보면, 재귀를 이용한 퇴각검색이 동작하는 방식과 굉장히 유사함을 알 수 있습니다.
실제 코드도 거의 비슷한 방식으로 짜게 됩니다.
시간복잡도는 인접 리스트를 이용할 경우, 모든 정점을 한 번씩 방문하게 되고, 다음 정점을 확인하는 과정에서 모든 간선을 두 번씩 확인하게 되므로 (간선 \((u,v)\)라면 \(u\)에서 한 번, \(v\)에서 한 번), 총 시간 복잡도는 \(O(|V|+2|E|) = O(|V|+|E|)\)입니다.
2. BFS (Breadth First Search)
BFS는 그래프를 "너비 우선"으로 탐색해 나가는 알고리즘 입니다.
특정한 정점을 시작으로 해서, 시작 정점과 바로 이웃한 정점들을 방문하고, 바로 이웃한 정점들과 이웃한 정점들을 방문하고, 같은 방식으로 시작 정점과 떨어진 거리에 따라 단계적으로 방문하게 됩니다.
역시 한번 방문한 정점은 다시 방문하지 않습니다.
그러면 위의 그래프를 BFS탐색한 결과는 다음과 같습니다.
$$\{1\} \rightarrow \{2\} \rightarrow \{3,5,6\} \rightarrow \{4\}$$
이걸 실제 코드로 구현하려면 어떻게 해야 할까요?
바로 큐(queue) 자료구조를 사용하여 다음과 같이 하면 됩니다.
1. 큐의 시작 정점을 삽입하고 시작합니다.
2. 큐의 제일 앞에 있는 원소를 탐색한 후, 이 원소에 연결되어 있으면서 아직 방문하지 않은 정점을 큐에 삽입합니다.
3. 맨 앞 원소를 삭제하고, 2번으로 되돌아갑니다.
4. 큐가 비어있으면 종료합니다.
그러면 연결되어 있는 모든 정점을 '단계별로' 방문할 수 있게 됩니다.
시간복잡도는 인접 리스트를 사용한 경우,
역시 모든 정점을 한 번씩, 모든 간선을 두 번씩 확인하게 되므로 DFS와 같이 \(O(|V|+|E|)\)입니다.
지금까지 DFS와 BFS탐색에 대해 알아 보았습니다. 그럼 이제 실제 코드를 짜보도록 합시다.
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
www.acmicpc.net
인접 행렬 사용한 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, st;
bool graph[1001][1001]; //인접 행렬
bool isVisited[1001]; // i번째 정점을 방문했는지 여부 저장
void DFS(int v) // 현재 정점 v를 보고 있다.
{
cout << v << ' ';
isVisited[v] = 1; // v를 방문했다.
for (int nv = 1; nv <= n; nv++) // 다른 모든 정점을 살펴본다.
{
if (graph[v][nv] && !isVisited[nv])
{
// v와 nv가 연결되어있고, nv를 아직 방문하지 않았다.
DFS(nv);
}
}
}
void BFS()
{
memset(isVisited, 0, sizeof isVisited); // isVisited 배열을 0으로 초기화해준다.
queue <int> q; // 큐 자료구조를 사용한다.
q.push(st); // 큐에 시작정점을 넣고 시작한다.
isVisited[st] = 1;
while (!q.empty()) // 큐가 빌때까지
{
int v = q.front(); // 현재 큐의 맨 앞 원소를 보고 있다.
cout << v << ' ';
for (int nv = 1; nv <= n; nv++) // 다른 모든 정점을 살펴본다.
{
if (graph[v][nv] && !isVisited[nv])
{
// v와 nv가 연결되어있고, nv를 아직 방문하지 않았다.
q.push(nv); // 큐의 맨 뒤에 추가한다.
isVisited[nv] = 1;
// (중요) 큐에 넣으면서 방문해줬다고 체크한다.
}
}
q.pop(); // 맨 앞 원소를 제거한다.
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> st;
for (int i = 0; i < m; i++)
{
int u, v; cin >> u >> v;
graph[u][v] = graph[v][u] = 1; // u와 v사이가 연결되어 있다.
}
DFS(st);
cout << '\n';
BFS();
}
|
인접 리스트 사용한 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m, st;
vector <int> graph[1001]; // 인접 리스트
bool isVisited[1001]; // i번째 정점을 방문했는지 여부 저장
void DFS(int v) // 현재 정점 v를 보고 있다.
{
cout << v << ' ';
isVisited[v] = 1; // v를 방문했다.
for (int nv : graph[v]) // v에 연결된 모든 정점을 살펴본다.
{
if (!isVisited[nv])
{
// v와 nv가 연결되어있고, nv를 아직 방문하지 않았다.
DFS(nv);
}
}
}
void BFS()
{
memset(isVisited, 0, sizeof isVisited); // isVisited 배열을 0으로 초기화해준다.
queue <int> q; // 큐 자료구조를 사용한다.
q.push(st); // 큐에 시작정점을 넣고 시작한다.
isVisited[st] = 1;
while (!q.empty()) // 큐가 빌때까지
{
int v = q.front(); // 현재 큐의 맨 앞 원소를 보고 있다.
cout << v << ' ';
for (int nv : graph[v]) // v에 연결된 모든 정점을 살펴본다.
{
if (!isVisited[nv])
{
// v와 nv가 연결되어있고, nv를 아직 방문하지 않았다.
q.push(nv); // 큐의 맨 뒤에 추가한다.
isVisited[nv] = 1;
// (중요) 큐에 넣으면서 방문해줬다고 체크한다.
}
}
q.pop(); // 맨 앞 원소를 제거한다.
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> st;
for (int i = 0; i < m; i++)
{
int u, v; cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
// u와 v사이가 연결되어 있다.
}
for (int i = 1; i <= n; i++)
{
sort(graph[i].begin(), graph[i].end());
//방문할 수 있는 정점이 여러개인 경우 정점 번호가 작은 것을 먼저 탐색하기 위해,
//인접 리스트를 정렬한다.
}
DFS(st);
cout << '\n';
BFS();
}
|
이제 DFS와 BFS을 이용해 풀 수 있는 문제들을 살펴보도록 합시다.
https://www.acmicpc.net/problem/11724
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
www.acmicpc.net
그래프 탐색으로 할 수 있는 가장 기본적인 작업은 컴포넌트의 개수를 세는 것입니다.
다시 말해서 이 그래프가 몇 개의 서로 이어지지 않은 덩어리들로 이루어져 있는지 셀 수 있습니다.
어떤 정점에서 시작해서 DFS나 BFS로 탐색을 하면 연결되어 있는 모든 정점이 방문 되기 때문에,
1번 정점부터 차례로 살펴보면서 아직 방문되지 않았다면 그 정점에서 시작하는 DFS나 BFS탐색을 시작하는 것을 반복합시다.
탐색을 총 몇 번했는지 세면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
vector <int> graph[1001]; // 인접 리스트
bool isVisited[1001];
void DFS(int v)
{
isVisited[v] = 1;
for (auto nv : graph[v])
{
if (!isVisited[nv]) DFS(nv);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v; cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int ans = 0;
for (int v = 1; v <= n; v++)
{
if (!isVisited[v])
{
ans++;
DFS(v);
// 아직 방문되지 않은 정점이 있다면 거기서부터 DFS를 시작한다.
}
}
cout << ans;
// 답은 탐색을 한 횟수이다.
}
|
위와 같이 문제에서 그래프라고 명시적으로 나와있지 않아도, 문제 상황을 그래프로 바꿔서 문제를 풀 수 있습니다.
다음 문제를 풀어봅시다.
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수
www.acmicpc.net
위와 비슷한 문제인데, 이번엔 문제에서 대놓고 그래프를 입력으로 주지 않습니다.
대신 격자판을 주고, 좌우나 위아래로 인접해 있는 칸이 연결된 단지라고 합니다.
이런 경우, 우리는 격자 칸 각각이 정점이고, 인접한 칸끼리 간선으로 연결되어 있는 그래프라고 생각할 수 있습니다.
그렇다고 각각의 칸을 하나의 정점 번호로 변환한 다음, 인접리스트 형태로 그래프를 새로 저장할 필요는 없습니다.
각 좌표 자체가 정점이라고 생각해봅시다.
예를 들어, 정점 \((x,y)\)를 위에서 \(x\)칸, 왼쪽에서 \(y\)칸 떨어진 칸이라고 할 수 있습니다.
그러면 정점 \((x,y)\)와 \((x-1,y)\), \((x+1,y)\), \((x,y-1)\), \((x,y+1)\)는 서로 연결되어 있음을 쉽게 알 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int n;
string graph[25];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
// 상하좌우로의 방향을 미리 저장해둔다.
int cnt = 0;
bool isVisited[25][25];
void DFS(int x, int y) // 정점 (x,y)를 보고 있다.
{
cnt++;
isVisited[x][y] = 1;
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
// 상하좌우 4방향에 대해 살펴본다.
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
// 지도를 벗어난다면 무시한다.
if (graph[nx][ny] == '0') continue;
// 단지가 없는 칸도 무시한다.
if (!isVisited[nx][ny])
{
DFS(nx, ny);
// 인접한 칸이 아직 방문되지 않았다면 계속 탐색한다.
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> graph[i];
vector <int> ans;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
{
//모든 칸을 살펴본다.
if (graph[i][j] == '0') continue; // 단지가 없는 칸이다.
if (!isVisited[i][j]) // 정점 (i,j)가 방문되지 않았다면
{
cnt = 0; // 집의 수를 초기화 한다.
DFS(i, j); // DFS 탐색
ans.push_back(cnt); // 집의 수를 저장한다.
}
}
sort(ans.begin(), ans.end()); // 집의 수를 오름차순 정렬한다.
cout << ans.size() << '\n';
for (int it : ans) cout << it << '\n';
}
|
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
BFS로만 할 수 있는 작업으로, 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있습니다.
BFS특성상 시작 정점에서 떨어진 순서대로 방문하기 때문에, 현재 정점까지의 거리를 저장해 놓음으로써 구현할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
int n, m;
string graph[101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int dist[101][101];
// 단순히 방문 여부를 판단하는 bool배열이 아니라, 시작지점에서부터 거리를 나타내는 배열
// -1이면 아직 방문하지 않았음을 나타낸다.
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> graph[i];
memset(dist, -1, sizeof dist);
// dist 배열을 -1로 초기화
queue <pair<int, int> > q;
// 정점 (x,y)를 큐에 저장한다.
q.push({ 0,0 });
dist[0][0] = 1; // 시작점까지의 거리를 1로 정의한다.
while (!q.empty()) // BFS
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
// 미로를 벗어나면 무시
if (graph[nx][ny] == '0') continue;
// 뚫린 칸이 아니면 무시
if (dist[nx][ny] == -1) // 아직 방문되지 않은 정점이라면
{
dist[nx][ny] = dist[x][y] + 1;
// 다음 정점까지의 거리는 현재 정점까지의 거리 + 1이다.
q.push({ nx,ny });
}
}
}
cout << dist[n - 1][m - 1];
// (n-1,m-1) 까지의 거리
}
|
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지
www.acmicpc.net
이번에도 문제를 그래프로 변환해 봅시다.
0부터 100000까지의 모든 점을 정점으로 정의한다면, 간선을 어떻게 정의할 수 있을까요?
모든 정점 \(x\)에서 \(x-1\), \(x+1\), \(x\times 2\)으로 가는 간선이 있다고 하면 될 것 같습니다.
그러면 수빈이의 위치 \(N\)에서 BFS탐색을 한 다음, 동생의 위치 \(K\)까지의 거리를 출력하면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n, k;
int dist[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
memset(dist, -1, sizeof dist);
queue <int> q;
q.push(n);
dist[n] = 0;
while (!q.empty())
{
int v = q.front(); q.pop();
// 현재 보고 있는 정점
if (v - 1 >= 0 && dist[v - 1] == -1)
{
// 정점 v-1을 아직 방문하지 않았다면 큐에 추가한다.
q.push(v - 1);
dist[v - 1] = dist[v] + 1;
}
if (v + 1 <= 100000 && dist[v + 1] == -1)
{
// 정점 v-1을 아직 방문하지 않았다면 큐에 추가한다.
q.push(v + 1);
dist[v + 1] = dist[v] + 1;
}
if (v * 2 <= 100000 && dist[v * 2] == -1)
{
// 정점 v-1을 아직 방문하지 않았다면 큐에 추가한다.
q.push(v * 2);
dist[v * 2] = dist[v] + 1;
}
}
cout << dist[k];
// k까지의 거리를 출력한다.
}
|
제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.
https://www.acmicpc.net/group/7712
ANZ1217
무슨 내용을 넣어야 좋을까요?
www.acmicpc.net
