HwanSeok

HwanSeok

Hwanseok Jang. Greate honour to graduate from the Korea Aerospace Univ. Write Code. Solve Problem

[BFS & DFS] 연결요소 이분 그래프

BFS와 DFS

Goal : 내 손이 제 멋대로 BFS와 DFS를 짜도록 만든다.

Warning Notice:
본 포스팅은 정확한 정의보다는 기억하기 쉬운 내용을 목적으로 합니다.

정의

DFS : 한 지점에서 갈 수 있을 때까지 계속 진행하고, 더이상 진행할 수 없으면 돌아온다.
BFS : 한 지점에서 이어져있는 모든 노드를 진행한 뒤, 다음 노드를 진행한다.

목적

Primary Notice: 모든 정점을 모두 한 번씩만 방문하는 것

DFS-BFS

DFS : Stack을 사용해서 구현

  1. 여러 개의 노드를 방문할 수 있을 때는 숫자가 작은 노드부터 방문한다고 가정한다.
  2. 모든 노드에 대해서 방문했는지 여부를 나타내는 check 배열을 만든다. 이때 check배열에서 0은 방문하지 않았음을, 1은 이미 방문했음을 의미한다.
  3. 시작 노드부터 방문하고, 방문한 노드는 스택에 넣는다.
  4. 방문한 노드의 check를 0에서 1로 바꾼다.
  5. 다시 인접한 노드 중 check가 1이 아닌 0.의 조건을 만족하는 노드를 방문하고 스택에 넣고 check를 1로 바꾼다.
  6. 만약 더이상 진행할 수 없는 경우 stack에서 top의 위치에 있는 노드에 대해서 판단한다. 판단 후 stack에서 top의 데이터를 pop한다.
  7. stack이 비어있으면 탐색을 종료한다. 혹은 모든 check가 1이면 탐색을 종료한다.

아래 코드는 인접행렬을 이용한 dfs입니다. a[x][i]는 해당 위치에 노드가 있는지 없는지를 판단하고, check[i]는 방문하지 않는 노드인 것을 확인합니다. 아래의 코드는 stack이 아닌 재귀호출을 사용해서 구현한 코드입니다.

1
2
3
4
5
6
7
8
9
10

void dfs(int x){
    check[x] = true;
    printf("%d ", x);
    for(int i=1; i<=n; i++){                      //C1
        if(a[x][i] == 1 && check[i] == false){ 
            dfs(i);
        }
    }
}
//c1 : 인접행렬에서는 a[0][0]의 값이 의미를 가지지 않는다. 그리고 현재 방문한 노드에 대해서 for문을 사용해서 모든 노드의 조건을 확인한다.

아래는 인접 리스트를 이용한 구현입니다. 인접 리스트 A[i]는 i와 연결된 정점들을 리스트로 포함하고 있습니다.

1
2
3
4
5
6
7
8
9
10
11

void dfs(int x){
    check[x] = true;
    printf("%d ", x);
    for(int i=0; i<a[x].size(); i++){
        int y = a[x][i];
        if(check[y]==false){
            dfs(y);
        }
    }
}

결과 : 1 -> 5 -> 4 -> 6 -> 3 -> 2

BFS : Queue를 사용해서 구현

  1. 큐에 넣을 때 방문했다고 체크해야 한다.
  2. 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식
  3. 시작 노드를 방문하고 큐에 넣는다.
  4. 시작 노드와 인접한 모든 노드를 방문했다고 생각하고 큐에 넣는다.
  5. 큐는 First In First Out이므로 시작 노드를 pop한다.
  6. 현재 큐에서 가장 앞에 있는 노드에 대해서 전체 과정을 다시 진행한다.
  7. 3.에서 시작 노드와 인접한 노드를 방문했다고 생각한 뒤, 큐에 넣었기 때문에 모든 노드가 큐에 한 번씩만 들어가고 다시 나온다.*

*만약 큐에서 나올 때 방문하는 것으로 생각하면 위 그래프 그림에서

  1. 1을 방문
  2. 2와 5를 큐에 넣음
  3. 2을 빼면서 2를 방문
  4. 2와 연결된 3과 5를 큐에 넣음 (check[5]는 아직 0이므로 큐에 들어감) 이와 같이 하나의 노드가 큐에 두 번 들어가는 문제점(하나의 노드를 두 번 방문하는 문제점)이 발생합니다.

아래 코드는 인접행렬을 이용한 bfs입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13

queue<int> q;
check[1] = true; q.push(1);
while(!q.empty()){
    int x = q.front(); q.pop(); 
    printf("%d ",x);
    for(int i=1; i<=n; i++){
        if(a[x][i] == 1 && check[i] ==false){
            check[i] = true;
            q.push(i);
        }
    }
}

아래 코드는 인접리스트를 이용한 bfs입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

queue<int> q;
check[1] = true; q.push();
while(!q.empty()){
    int x = q.front(); q.pop();
    printf("%d ",x);
    for(int i=0; i< a[x].size(); i++){
        int y = a[x][i];
        if(check[y] == false){
            check[y] = true;
            q.push(y);
        }
    }
}

결과 : 1 -> 5 -> 2 -> 4 -> 3 -> 6

시간 복잡도

두 알고리즘의 목표는 모든 정점을 한 번씩만 방문하는 것입니다. DFS 함수는 하나의 정점을 방문하고 출력한 뒤, 다시 방문해야하는 노드가 있는지 검사를 합니다. 따라서 DFS()함수는 Node의 갯수만큼 $V$번 호출됩니다. 따라서 O($V$)에 DFS 내부의 복잡도를 곱하면 최종적인 시간 복잡도를 얻을 수 있습니다.

DFS : 인접행렬 : 각 노드마다 연결된 노드를 찾기 위해서 모든 노드를 점검해야하므로 $O(VxV) = O(V^2)$의 시간 복잡도를 가집니다. DFS : 인접리스트 : 역시 각 노드마다 연결된 노드만큼 탐색을 진행합니다. 하지만 a[x][i]에 저장된 연결된 Edge의 갯수는 노드마다 다릅니다. 따라서 $O(VE)$가 절대 아닙니다. 인접리스트에서는 모든 노드를 점검하면서 연결된 노드를 탐색하는데 모든 에지는 각 두 번씩 인접리스트에 포함됩니다. 따라서 $O(V+2E) = O(V+E)$의 시간 복잡도를 가집니다.

BFS도 마찬가지 입니다. 같은 이유로 아래의 시간 복잡도를 가집니다.

BFS : 인접행렬 :$O(V^2)$ BFS : 인접리스트 : $O(V+E)$

백준 문제 1260번

  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

#include <iostream>
#include <queue>
using namespace std;
int N, M;
int node[1000 + 1];
bool check[1000 + 1];
int edge[1000 + 1][1000 + 1];

void dfs(int x) {
	check[x] = true; //방문했는지 안했는지는 노드기준으로. 에지 기준 아님
	printf("%d ", x);
	for (int i = 1; i < N + 1; i++) {//모든 노드에 대해서
		if (edge[x][i] == 1 && check[i] == false) {//현재 노드에서 다른 노드로 가는 길이 있고, 그 길을 안갔으면
			dfs(i);
		}
	}
}

void bfs(int x) { //여기선 false가 방문한 상태
	queue<int> q;
	check[x] = false;
	q.push(x);
	while (!q.empty()) {
		x = q.front(); q.pop(); //q의 front를 빼서 그 값을 탐색.
		printf("%d ", x);
		for (int i = 1; i < N + 1; i++) {//이번 x와 인접한 모든 노드를 다 q에 넣는다.
			//해당 노드를 방문할 때 q에 넣으면 강의에서 설명한 것처럼 같은 노드가 q에 두 번 들어가는 경우가 생긴다.
			if (edge[x][i] == 1 && check[i] == true) {
				check[i] = false;
				q.push(i);
			}
		}
	}
}

int main(void) {
	int V = 0;
	int es = 0, ee = 0; //edge start , edge end
	scanf("%d %d %d", &N, &M, &V);

	for (int i = 1; i < M + 1; i++) {
		node[i] = i; //노드 번호 부여
		scanf("%d %d", &es, &ee);
		edge[es][ee] = 1; //에지 저장
		edge[ee][es] = 1; //양방향 에지 저장
	}
	dfs(V);
	printf("\n");
	bfs(V);

	return 0;
}
  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

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
vector<int> a[1001];
bool check[1001];
void dfs(int node) {
	check[node] = true;
	printf("%d ", node);
	for (int i = 0; i < a[node].size(); i++) {
		int next = a[node][i];
		if (check[next] == false) {
			dfs(next);
		}
	}
}
void bfs(int start) {
	queue<int> q;
	memset(check, false, sizeof(check));
	check[start] = true;
	q.push(start);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		printf("%d ", node);
		for (int i = 0; i < a[node].size(); i++) {
			int next = a[node][i];
			if (check[next] == false) {
				check[next] = true;
				q.push(next);
			}
		}
	}
}
int main() {
	int n, m, start;
	scanf("%d %d %d", &n, &m, &start);
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		sort(a[i].begin(), a[i].end());
	}
	dfs(start);
	puts("");
	bfs(start);
	puts("");
	return 0;
}

연결 요소 Connected Component

노드 1,2,3,4,5,6은 다음과 같은 조건으로 서로 연결되어있습니다.

  1. 노드 1,2,3은 삼각형으로 이루어져있다.
  2. 노드 4,5,6은 삼각형으로 이루어져있다.

  3. 두 삼각형은 연결되어있지 않다. 이 때 전체 그래프에서 연결 요소의 갯수를 찾는 방법은 아래와 같습니다.

  4. 한 점에서 BFS나 DFS를 진행합니다. 예를 들어 1에서 시작합니다.
  5. 연결요소의 갯수를 +1합니다.
  6. 탐색을 하는 동안 1,2,3의 check는 true가 됩니다. 탐색이 종료합니다.
  7. 다음으로 노드 2에서 시작하려고하는데 이미 true여서 탐색하지도 않고 연결 요소 갯수도 그대로 입니다.
  8. 3도 마찬가지로 지나가고 4에서는 check가 false이므로 탐색을 진행하고 갯수도 하나 늘립니다.

백준 11724번

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

/*
2019-04-09
장환석

문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력
첫째 줄에 연결 요소의 개수를 출력한다.

	
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int N, M, u, v, ans=0;
vector<int> a[1001];
bool check[1001];

void dfs(int x) { 
	check[x] = true;
	
	for (int i = 0; i <a[x].size(); i++) {
		if (check[a[x][i]] == false) {
			dfs(a[x][i]);
		}
	}
}

void bfs(int x) {
	queue<int> q;
	check[x] = true;
	q.push(x);
	while (!q.empty()) {
		int y = q.front(); q.pop();
		for (int i = 0; i < a[y].size(); i++) {
			if (check[a[y][i]] == false) {
				check[a[y][i]] = true;
				q.push(a[y][i]);
			}
		}
	}

}



int main(void) {
	scanf_s("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf_s("%d %d", &u, &v);
		a[u].push_back(v);
		a[v].push_back(u);
	}

	//정렬
	for (int i = 1; i <= N; i++) {
		sort(a[i].begin(), a[i].end());
	}

	//모든 점에 대해서 한번씩 확인하면서 connected components를 찾는다
	for (int i = 1; i <= N; i++) {
		if (check[i] == false) {
			ans += 1;
			bfs(i);
		}
	}
	printf("%d ", ans);
	return 0;
}

이분 그래프 Bipartite Graph

그래프를 아래와 같은 조건으로 A와 B로 나눌 수 있으면 이분그래프라고 합니다.

  1. A에 포함되어 있는 정점끼리는 간선이 없다.
  2. B에 포함되어 있는 정점끼리는 간선이 없다.
  3. 모든 간선의 한 점은 A에, 다른 한 점은 B에 속한다.

bipartite

그리고 아래와 같이 생긴 그래프로 이분 그래프입니다.

A —간선— B

G —간선— D

C —간선— E

탐색은 아래와 같이 진행합니다.

  1. 예상되는 두 개의 그룹에 각각 빨간색과 파란색을 부여합니다.
  2. 하나의 점에서 시작합니다. 현재의 노드를 빨간색으로 칠합니다.
  3. 현재 노드에서 갈 수 있는 어떤 노드를 탐색을 하고 파란색으로 칠합니다.
  4. 현재 노드에서 방문할 수 있는 노드를 하나 선택해서 방문하고 빨간색으로 칠합니다.
  5. 만약 더 갈 수 있는 노드가 없다면 BFS 알고리즘을 통해서 찾습니다.
  6. 더이상 접근할 수 있는 노드가 없을 때까지 진행합니다.
  7. 마지막 노드에서 연결된 모든 노드들의 색을 검사해서 마지막 노드의 색과 다른 색인지 판단합니다.

정리하면,

  1. 방문하지 않은 정점이면 방문하고 적절한 색을 칠합니다.
  2. 방문한 정점이면 색만 검사하고 다음 탐색을 진행합니다.
  3. 더이상 검사를 할 노드가 없으면 종료합니다.

백준 1707번

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

/*
2019-05-04
장환석

문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

vector<int> a[20001];
int color[20001]; //0 :defulat, 1, Group A, 2: Group 2

void dfs(int node, int c) {
	color[node] = c;
	for (int i = 0; i < a[node].size(); i++) {
		int next = a[node][i];
		if (color[next] == 0) {
			dfs(next, 3 - c);
		}
	}
}



int main(void) {
	int K, V, E, u, v;
	scanf("%d ", &K);
	while (K--) {
		
		scanf("%d %d", &V, &E);

		for (int i = 1; i <= V; i++) {
			a[i].clear();
			color[i] = 0;
		}
		
		for (int i = 0; i < E; i++) {
			scanf("%d %d", &u, &v);
			a[u].push_back(v);
			a[v].push_back(u);
		}

		//색칠한다.
		for (int i = 1; i <= V; i++) {
			if (color[i] == 0) {
				dfs(i, 1);
			}
		}

		//검사한다.
		bool OK = true;
		for (int i = 1; i <= V; i++) {
			for (int j = 0; j < a[i].size(); j++) {
				int y = a[i][j];
				if (color[i] == color[y]) {
					OK = false;
				}
			}
		}

		printf("%s\n", OK ? "YES" : "NO");
	}
	return 0;
}

Leave a comment

You may also enjoy