백준 알고리즘 기초 - 그래프1 (BFS, DFS)

여기저기 탐색 해보기

그래프 챕터의 시작이다.

BFS, DFS 가 꽤나 중요한 알고리즘이기도 하고,

그래프 문제가 어려워지면 끝도 없다는 말을 들었기에

확실하게 하고 넘어가야 할 것 같다.

정리 시작!

-

* 그래프 : 자료구조의 일종. 어떻게 문제 상황을 구조화 하는지가 관건이다.

 - 정점 (node, vertex), 간선 (edge) : 정점간의 관계

 - 경로 (path), 사이클 / 단순 경로, 단순 사이클 : 같은 정점을 두 번 이상 방문하지 않은 것

 - 차수 : 정점과 연결되어 있는 간선의 개수

 

* 그래프의 표현

 - 인접 행렬 : V * V 크기의 이차원 배열 이용. 간선 있으면 1, 없으면 0.

 - 인접 리스트 : A[i]에 i와 연결된 정점을 리스트로 포함하고 있음. 크기를 동적으로 변경할 수 있어야 함. 인접 행렬에 비해 탐색 속도가 빠르고 공간도 덜 차지함.

 - 간선 리스트 : 배열을 이용해서 구현. 간선을 모두 저장하고 있음. 그리 많이 쓰지는 않음.

예제를 풀어보자.

 

- ABCDE (mid) : 친구 관계를 입력하고 제시된 친구 관계가 존재하는지 구하는 문제다.

13023번: ABCDE

 - 인접 행렬, 인접 리스트, 간선 리스트를 모두 사용해서 구한다. 기초적인 개념이지만 어떤 식으로 접근해야 할지 꽤나 고민을 많이 했다. 예제 코드를 보면서 이해해보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool a[2000][2000]; // 인접행렬
vector <int> g[2000]; // 인접리스트
vector <pair<int, int> > edges; // 간선리스트
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;
		edges.push_back({ from, to });
		edges.push_back({ to, from });
		a[from][to] = a[to][from] = true;
		g[from].push_back(to);
		g[to].push_back(from);
	}
	m *= 2;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			// A -> B
			int A = edges[i].first;
			int B = edges[i].second;
			// C -> D
			int C = edges[j].first;
			int D = edges[j].second;
			if (A == B || A == C || A == D || B == C || B == D || C == D) {
				continue;
			}
			// B -> C
			if (!a[B][C]) {
				continue;
			}
			// D -> E
			for (int E : g[D]) {
				if (A == E || B == E || C == E || D == E) {
					continue;
				}
				cout << 1 << '\n';
				return 0;
			}
		}
	}
	cout << 0 << '\n';
	return 0;
}

 - 일단 인접 행렬, 인접 리스트, 간선 리스트에 입력한 수를 넣어준다.

 - A<->B<->C<->D<->E 와 같은 관계가 있는지 확인하려면 어떻게 해야할까? 3가지 방법을 다 쓰려면 각 방법이 갖는 장점을 활용해서 접근해보면 되겠다. 먼저 A와 B, C와 D가 각각 친구인지 확인한다. 간선 리스트를 활용해서 노드를 지정해주고, 중복되는 노드가 없는지도 확인한다.

 - 이 단계를 지났다면 A와 B, C와 D는 각각 연결이 확인됐다. 다음으로 B와 C의 관계를 확인한다. 인접 행렬을 활용해 존재 여부만 파악하면 된다. 그럼 A-B-C-D 의 관계는 확인이 됐다. 마지막으로 D와 E의 관계를 확인한다. 인접 리스트를 활용해 D에 연결된 노드 중 하나를 택했을 때, 다른 노드와 중복되지 않는 경우를 생각해준다.

 - 모든 단계를 통과했다면 1을 출력하고, 통과하지 못 했다면 0을 출력하면 된다.

 

* 그래프의 탐색 : DFS, BFS 로 나뉜다.

 - DFS : 깊이 우선 탐색. 스택 이용. 갈 수 있는만큼 최대한 많이 가고, 갈 수 없으면 이전 노드로 돌아간다.

 - 재귀 호출로 구현하는데 인접 행렬을 활용하면,

void dfs(int x) {
	check[x] = true;
    for(int i=1; i<=n; i++) {
    	if (a[x][i] == 1 && check == false) {
        	dfs(i);
        }
    }    
}    

 - 해당 위치의 노드에 방문 표시를 하고, 그 노드의 간선 중에서 방문하지 않은 곳에 재귀적으로 방문한다.

 - 인접 리스트를 활용해서 구현할 수도 있다.

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

 - 위와 비슷한데, 해당 노드의 크기만큼만 확인한다는 점이 다르다.

 

 - BFS : 너비 우선 탐색. 큐 이용. 지금 위치에서 갈 수 있는 모든 곳에 간다.

 - 인접 행렬을 활용해 구현하면,

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

 - 인수로 들어가는 n이 출발 노드다. 해당 노드의 간선 중에서 방문하지 않은 곳은 다 방문하고 큐에 넣는다. 이를 큐가 빌 때까지 반복해주면 된다.

 - 인접 리스트를 활용하면,

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

 - dfs에서 한 거랑 똑같은 원리로 변환해주면 된다. 예제 하나 풀고 마무리 해보자.

 

* DFS 와 BFS (mid) : dfs와 bfs 에 대해 알고 있는지 확인하는 문제다.

1260번: DFS와 BFS

 - 간선이 여러 개일 때는 정점 번호가 작은 것부터 방문하라는 조건이 있다. 인접 리스트를 쓰면 입력 순서에 따라 조건을 만족하지 못 할 수도 있으므로, 이럴 때는 인접 행렬을 사용하는 게 편하다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int s[1001][1001];
int n, m, v;

bool check[1001];

void dfs(int x) {
	cout << x << ' ';
	check[x] = true;
	for (int i = 1; i <= n; i++) {
		if (s[x][i] == 1 && check[i] == false) {
			dfs(i);
		}
	}
}

void bfs(int k) {
	queue<int> q;
	check[k] = true;
	q.push(k);
	while (!q.empty()) {
		int x = q.front();
		cout << x << ' ';
		q.pop();
		for (int i = 1; i <= n; i++) {
			if (s[x][i] == 1 && check[i] == false) {
				check[i] = true;
				q.push(i);
			}
		}
	}
}

int main()
{
	cin >> n >> m >> v;

	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		s[a][b] = 1;
		s[b][a] = 1;
	}

	dfs(v);
	cout << '\n';
	memset(check, 0, 1001);
	bfs(v);

	return 0;
}

 - 언제 출력을 해야 모두 출력할 수 있을지만 생각해주면 쉽게 풀린다.

-

dfs, bfs 는 할 때마다 디테일한 부분이 잘 기억이 안 나서 다시 확인하게 된다.

확실히 복습해서 이번에 제대로 개념을 잡아놓자...!

진도 쭉쭉 나가보자.

정리 끝!