[BFS & DFS] 연결요소 이분 그래프
BFS와 DFS
Goal : 내 손이 제 멋대로 BFS와 DFS를 짜도록 만든다.
Warning Notice:
본 포스팅은 정확한 정의보다는 기억하기 쉬운 내용을 목적으로 합니다.
정의
DFS : 한 지점에서 갈 수 있을 때까지 계속 진행하고, 더이상 진행할 수 없으면 돌아온다.
BFS : 한 지점에서 이어져있는 모든 노드를 진행한 뒤, 다음 노드를 진행한다.
목적
Primary Notice: 모든 정점을 모두 한 번씩만 방문하는 것
DFS : Stack을 사용해서 구현
- 여러 개의 노드를 방문할 수 있을 때는
숫자가 작은 노드부터 방문한다고 가정한다. - 모든 노드에 대해서 방문했는지 여부를 나타내는 check 배열을 만든다. 이때 check배열에서 0은 방문하지 않았음을, 1은 이미 방문했음을 의미한다.
- 시작 노드부터 방문하고, 방문한 노드는 스택에 넣는다.
- 방문한 노드의 check를 0에서 1로 바꾼다.
- 다시 인접한 노드 중 check가 1이 아닌 0.의 조건을 만족하는 노드를 방문하고 스택에 넣고 check를 1로 바꾼다.
- 만약 더이상 진행할 수 없는 경우 stack에서 top의 위치에 있는 노드에 대해서 판단한다. 판단 후 stack에서 top의 데이터를 pop한다.
- stack이 비어있으면 탐색을 종료한다. 혹은 모든 check가 1이면 탐색을 종료한다.
아래 코드는 인접행렬을 이용한 dfs입니다. a[x][i]는 해당 위치에 노드가 있는지 없는지를 판단하고, check[i]는 방문하지 않는 노드인 것을 확인합니다. 아래의 코드는 stack이 아닌 재귀호출을 사용해서 구현한 코드입니다.
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와 연결된 정점들을 리스트로 포함하고 있습니다.
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를 사용해서 구현
- 큐에 넣을 때 방문했다고 체크해야 한다.
- 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식
- 시작 노드를 방문하고 큐에 넣는다.
- 시작 노드와 인접한 모든 노드를 방문했다고 생각하고 큐에 넣는다.
- 큐는 First In First Out이므로 시작 노드를 pop한다.
- 현재 큐에서 가장 앞에 있는 노드에 대해서 전체 과정을 다시 진행한다.
- 3.에서 시작 노드와 인접한 노드를 방문했다고 생각한 뒤, 큐에 넣었기 때문에 모든 노드가 큐에 한 번씩만 들어가고 다시 나온다.*
*만약 큐에서 나올 때 방문하는 것으로 생각하면 위 그래프 그림에서
- 1을 방문
- 2와 5를 큐에 넣음
- 2을 빼면서 2를 방문
- 2와 연결된 3과 5를 큐에 넣음 (check[5]는 아직 0이므로 큐에 들어감) 이와 같이 하나의 노드가 큐에 두 번 들어가는 문제점(하나의 노드를 두 번 방문하는 문제점)이 발생합니다.
아래 코드는 인접행렬을 이용한 bfs입니다.
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입니다.
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번
- 인접행렬 코드
#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;
}
- 인접리스트 코드
#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,2,3은 삼각형으로 이루어져있다.
- 노드 4,5,6은 삼각형으로 이루어져있다.
-
두 삼각형은 연결되어있지 않다. 이 때 전체 그래프에서 연결 요소의 갯수를 찾는 방법은 아래와 같습니다.
- 한 점에서 BFS나 DFS를 진행합니다. 예를 들어 1에서 시작합니다.
- 연결요소의 갯수를 +1합니다.
- 탐색을 하는 동안 1,2,3의 check는 true가 됩니다. 탐색이 종료합니다.
- 다음으로 노드 2에서 시작하려고하는데 이미 true여서 탐색하지도 않고 연결 요소 갯수도 그대로 입니다.
- 3도 마찬가지로 지나가고 4에서는 check가 false이므로 탐색을 진행하고 갯수도 하나 늘립니다.
백준 11724번
/*
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로 나눌 수 있으면 이분그래프라고 합니다.
- A에 포함되어 있는 정점끼리는 간선이 없다.
- B에 포함되어 있는 정점끼리는 간선이 없다.
- 모든 간선의 한 점은 A에, 다른 한 점은 B에 속한다.
그리고 아래와 같이 생긴 그래프로 이분 그래프입니다.
A —간선— B
G —간선— D
C —간선— E
탐색은 아래와 같이 진행합니다.
- 예상되는 두 개의 그룹에 각각 빨간색과 파란색을 부여합니다.
- 하나의 점에서 시작합니다. 현재의 노드를 빨간색으로 칠합니다.
- 현재 노드에서 갈 수 있는 어떤 노드를 탐색을 하고 파란색으로 칠합니다.
- 현재 노드에서 방문할 수 있는 노드를 하나 선택해서 방문하고 빨간색으로 칠합니다.
- 만약 더 갈 수 있는 노드가 없다면 BFS 알고리즘을 통해서 찾습니다.
- 더이상 접근할 수 있는 노드가 없을 때까지 진행합니다.
- 마지막 노드에서 연결된 모든 노드들의 색을 검사해서 마지막 노드의 색과 다른 색인지 판단합니다.
정리하면,
- 방문하지 않은 정점이면 방문하고 적절한 색을 칠합니다.
- 방문한 정점이면 색만 검사하고 다음 탐색을 진행합니다.
- 더이상 검사를 할 노드가 없으면 종료합니다.
백준 1707번
/*
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;
}