그래프 (재귀, 비재귀 DFS)

1. 그래프의 특징과 종류

---

방향이 있는 그래프

 

가중치가 있는 그래프

 

순환이 있는 그래프

 

 

2. 그래프 구현

---

2 - 1. 인접 행렬을 이용한 그래프

• 배열의 인덱스는 노드
  • 세로 방향 출발 노드
  • 가로 방향 도착 노드
• 배열의 값은 노드의 가중치

 

2 - 2. 인접 리스트를 이용한 그래프

 

 

결론

• 인접 행렬
  • 크기가 고정되어 있기 때문에 노드가 많고 연결이 적은 그래프에서 낭비가 심한 단점이 있다.
  • 간선의 정보를 O(1)에 얻을 수 있는 장점이 존재
• 인접 리스트
  • 대부분의 경우 인접 행렬에 비해 메모리를 절약할 수 있다.
  • 평균적으로 간선의 정보를 얻는데 시간이 좀 더 걸림

 

 

3. 그래프 탐색

---

3 - 1. BFS

• 최단 경로를 보장하는 탐색 방식
• queue를 사용한다.
• 방문 처리를 queue에 push할때 진행한다.

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

vector<char> answer;
vector<char> board[30];
unordered_map<char, int> vis;

void bfs(char cur)
{
	queue<char> q;
	q.push(cur);
	vis.insert({ cur, 1 });
	answer.push_back(cur);

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();

		for (auto nxt : board[cur])
		{
			if (vis.find(nxt) != vis.end())
				continue;
			q.push(nxt);
			vis.insert({ nxt, 1 });
			answer.push_back(nxt);
		}
	}
}

vector<char> solution(vector<pair<char, char>> graph, char start)
{
	for (int i = 0; i < graph.size(); ++i)
	{
		board[graph[i].first].push_back(graph[i].second);
	}

	bfs(start);

	return answer;
}


int main()
{
	vector<pair<char, char>> graph = { {'a','b'}, {'a','c'},{'b','d'},{'b','e'}, { 'c','f' },{'c','g'},{'d','h'}, { 'e','h' },{'f','i'},{'g','i'} };
	vector<char> ans = solution(graph, 'a');

	for (auto a : ans)
		cout << a << " ";
}

 

3 - 2. DFS

• 코딩 테스트에서 최단 경로 문제가 아닌 경우 처음으로 시도해보면 좋은 방식
• stack을 사용한다. or 재귀
• 방문 처리를 stack에서 pop 한 후 진행한다. (재귀가 아닌 방식에서!!)

dfs를 재귀 버전과 재귀가 아닌 버전 두가지로 구현할 수 있다.

• 재귀
  
  • 갈 수 있는 곳이 여러 곳이라면 번호가 낮은 순서부터 방문
  • 실제 방문을 할 때 방문 표시를 남긴다!!!
  • 우리가 개념적으로 알고있는 DFS의 순서로 진행한다. (가장 깊은곳으로 먼저 들어가는 방식)
• 비 재귀
  • 단순히 bfs 코드에서 queue만 stack으로 바꾼 경우 우리가 원하는 대로 동작하지 않는다!!
  • 비 재귀 방식을 이렇게 구현하면, 방문하기 전에 방문하지 않은 곳을 발견하면, 방문 표시를 남겨버리는 특징 때문이다.
  • 이 경우, 개념적으로 알고있는 DFS와 순서가 다르기 때문에 아래와 같이 구현하면 된다.
    
    • 처음 들어온 값에 대해서도 방문처리를 하지 않고,
    • stack에서 pop 한 후 방문처리를 해주면 된다.

주의점) 

• 실제로 정확한 방문 순서는 다르지만, 깊이를 우선적으로 탐색하는 탐색 방향성은 같다.
• 또한 그래프에 방향성이 있는 경우는 adj 라는 배열을 구성할 때 아래와 같이 구성하면 되지만
• 방향성이 없는 경우 아래와 같이 처리해 주어야 한다.
  • adj[vec[i][0]].push_back(vec[i][1]);
  • adj[vec[i][1]].push_back(vec[i][0]);

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> adj[10];
bool vis[10];
vector<int> answer;

void dfs(int cur)
{
	stack<int> st;
	st.push(cur);

	while (!st.empty())
	{
		int cur = st.top();
		st.pop();

		if (vis[cur])
			continue;
		vis[cur] = 1;
		answer.push_back(cur);

		for (int nxt : adj[cur])
		{
			if (vis[nxt])
				continue;
			st.push(nxt);
		}
	}
}

void dfs_recursive(int cur)
{
	vis[cur] = 1;
	answer.push_back(cur);

	for (int nxt : adj[cur])
	{
		if (vis[nxt])
			continue;
		dfs(nxt);
	}
}

int main()
{
	vector<vector<int>> vec = { {1,2},{1,3},{2,4},{2,5},{3,6} };

	for (int i = 0; i < vec.size(); ++i)
	{
		adj[vec[i][0]].push_back(vec[i][1]);
	}

	dfs_recursive(1);
	//dfs(1);

	for (auto a : answer)
		cout << a << " ";
}