[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - DFS와 BFS (1260)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - DFS와 BFS (1260)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - DFS와 BFS (1260)

 

---

1260번: DFS와 BFS

[ 문제 ]

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

[ 입력 ]

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

[ 출력 ]

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

---

[ 코드 1 - 인접 리스트 구현 ]

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring> // memset 사용을 위해
#include<queue>
using namespace std;

// index 0은 사용하지 않으므로, 배열을 1개 더 추가 (1001개)
vector <int> a[1001]; // 인접리스트 구현
bool check[1001];

/* DFS(깊이우선탐색) : 재귀함수 구현 */
void dfs(int node) {  // 탐색 시작 노드를 삽입
	check[node] = true; // 탐색시작노드 방문처리
	cout << node <<" "; // 방문 노드 출력

	for (int i = 0; i < a[node].size(); i++) // a[node]와 연결된 개수(size)만큼
		// node와 연결될 것이 없으면, 자동으로 for문 작동 x
	{
		int next = a[node][i]; 
		if (check[next] == false) // next 정점을 아직 방문하지 않았을 경우 진행
		{
			dfs(next);
		}
	}
}

/* 장점
 1. 단지 현 경로상의 노드만을 기억하면 되므로, 저장공간의 수요가 비교적 적다.
 2. 목표노드가 깊은 단계에 있을 경우, 해를 빨리 구할 수 있다. */

/* 단점
 1. 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수도 있다.
 2. 얻어진 해가 최단경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다.*/




/* BFS(너비우선탐색) : 큐를 이용하여 구현 */
void bfs(int start) { // 시작 노드 방문 후, 시작 노드에 있는 인접한 모든 노드들을 우선으로 방문함
	queue <int> q;
	memset(check, false, sizeof(check)); // false로 모두 변경

	check[start] = true; // 탐색시작노드 방문처리
	q.push(start);

	while (!q.empty())
	{
		int node = q.front(); // 현재 node = q의 가장 앞에 있는 것
		q.pop(); // q를 해당 노드에서 빼기
		cout << node << " "; // 방문 노드 출력

		for (int i = 0; i < a[node].size(); i++) // a[node]와 연결된 개수(size)만큼
		{
			int next = a[node][i]; // 다음 인접노드 탐색 (배열 하나하나 탐색)
			if (check[next] == false) // 다음 탐색할 부분에 아직 방문하지 않았다면
			{
				check[next] = true; // 탐색 방문 처리
				q.push(next); // next를 큐에 넣기
			}
		}
	}
}

/*장점
 1. 출발노드에서 목표노드까지의 최단 길이 경로를 보장 */

/*단점
1. 경로가 길 경우에는 탐색 가지가 급격히 증가함에 따라, 보다 많은 기억 공간을 필요
2. 해가 존재하지 않는다면, 유한 그래프의 경우, 모든 그래프를 탐색한 후에 실패로 끝난다.
3. 무한그래프의 경우에는 결코 해를 찾지도, 끝내지도 못한다. */



int main() {
	int N, M, V; // 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V
	cin >> N >> M >> V;

	for (int i = 0; i < M; i++)
	{
		int u, v;
		cin >> 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(V);
	cout << '\n';
	bfs(V);
	cout << '\n';
	return 0;
}

[ 코드 2 - 간선 리스트 구현 ] 

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring> // memset 사용을 위해
#include<queue>
using namespace std;

/* 간선 리스트 사용 */
class Edge {
public:
	int from, to;
};

Edge edge[20001]; // 각 간선은 x,y를 잇고 있다. 즉, 객체마다의, from, to 변수에 각각 저장
// 간선의 개수는 (최대값) 10000개 x 2 (양방향) = 20000개
int cnt[1001]; // 간선을 정렬한 후, 각 점에서 시작하는 간선의 첫 인덱스
bool check[1001];

// 클래스(구조체)를 위한 비교함수
// 비교 함수 만든 것 (주의 : const & 연산자를 사용해야 한다 - 값의 수정이나 변경이 X기 때문. 단순 비교)
bool cmp(const Edge& u, const Edge& v) {
	if (u.from == v.from) // 만약 from이 가다면
	{
		return u.to < v.to; // to를 비교해서 오름차순으로 정렬해라.
	}
	else // 만약 from이 같지 않다면
	{
		return u.from < v.from; // from을 비교해서 오름차순으로 정렬해라.
	}
}

/* DFS - 간선 리스트 구현 */
void dfs(int node) {
	check[node] = true;
	cout << node << " ";

	for (int i = cnt[node - 1]; i < cnt[node]; i++) // node로 시작하는 간선을 돌려보기
	{
		int next = edge[i].to;
		if (check[next] == false)
		{
			dfs(next);
		}
	}
}

/* BFS - 간선 리스트 구현 */
void bfs(int start) {
	queue <int> q;
	q.push(start);
	check[start] = true;

	while (!q.empty())
	{
		int node = q.front();
		q.pop();
		cout << node << " ";

		for (int i = cnt[node - 1]; i < cnt[node]; i++)
		{
			int next = edge[i].to; // node와 연결된 값들 중, 거쳐가지 않은 값들에 대해 진행
			if (check[next] == false)
			{
				check[next] = true;
				q.push(next);
			}
		}
	}
}

int main() {
	int n, m, start;
	cin >> n >> m >> start; // 정점의 개수 : N, 간선의 개수 : M, 탐색을 시작할 정점의 번호 start

	// 일단 모든 간선 저장
	for (int i = 0; i < m; i++)
	{
		// 해당 값이 A - B로 연결되는 경우
		scanf("%d %d", &edge[i].from, &edge[i].to);
		// 해당 값이 B - A로 연결되는 경우
		edge[i + m].from = edge[i].to;
		edge[i + m].to = edge[i].from;
	}

	m *= 2; // 간선의 개수 x 2 => 2배를 해주면 양방향의 간선의 개수가 만들어지는 것

	// 저장된 간선 오름차순 정렬
	sort(edge, edge + m, cmp); // 클래스를 정렬하기 위해 (edge부터 edge+m까지)

	for (int i = 0; i < m; i++)
	{
		cnt[edge[i].from] += 1; // edge[i].from으로 시작하는 간선 +1하기 (각각 시작하는 간선 개수 세기)
	}


	for (int i = 1; i <= n; i++) // 정점은 1부터 시작하므로, 이것도 1부터 시작
	{
		cnt[i] += cnt[i - 1]; // i번정점과 연결된 간선에 대해 찾아주기 위해 만들어주는 배열 (이전의 값들을 더해줌)
		// ex. cnt[1] = 2, cnt[2] = 6이면, 2번 정점은 cnt[2] ~ cnt[3]-1개까지라고 이야기할 수 있음
	}


	dfs(start);
	cout << '\n';
	memset(check, false, sizeof(check));
	bfs(start);
	cout << '\n';

	return 0;
}

[ 코드 3 - 비재귀 구현 1 ]

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring> // memset 사용을 위해
using namespace std;

vector <int> a[1001]; // 저장공간
bool check[1001];

void dfs(int node) {
	// 스택을 사용하면 재귀함수를 사용하지 않아도 됨.
	stack <pair<int, int>> s;
	// pair<int,int> : 2개의 각각 지정한 타입을 저장함. (first, second로 호출 가능)
	s.push(make_pair(node, 0));

	check[node] = true;
	cout << node << ' ';

	while (!s.empty())
	{
		int node = s.top().first;
		int start = s.top().second;

		s.pop();

		for (int i = start; i < a[node].size(); i++)
		{
			int next = a[node][i];
			if (check[next] == false)
			{
				cout << next << ' ';
				check[next] = true;
				
				s.push(make_pair(node, i + 1)); // 다음번에 a[node][i+1]을 수행할 수 있도록 스택에 넣어놓음 (for문을 탈출하기 때문에)
				s.push(make_pair(next, 0)); // next값을 수행할 수 있도록 스택에 넣어놓음

				break; // for문 탈출
			}
		}
	}
}


void bfs(int start) {
	queue<int> q;
	check[start] = true;
	q.push(start);

	while (!q.empty())
	{
		int node = q.front();
		q.pop();
		cout << 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;
	cin >> n >> m >> start;

	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> 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);
	cout << '\n';
	memset(check, false, sizeof(check));
	bfs(start);
	cout << '\n';

	return 0;

}