[백준 - 1260] DFS와 BFS

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <algorithm>
#define MAX_NODE 1'001
#define MAX_EDGE 10'001
typedef short integer;
using namespace std;

integer N, M, V;

priority_queue<integer,vector<integer>,greater<integer>> node[MAX_NODE];
priority_queue<integer,vector<integer>,greater<integer>> node2[MAX_NODE];
bool bIsVisit[MAX_NODE]{ false };
bool result = false;
void Dfs(const int & num)
{
	cout << num << ' ';
	bIsVisit[num] = true;
	while (node[num].empty() == false)
	{
		if (bIsVisit[node[num].top()] == false)
		{
			Dfs(node[num].top());
		}
		node[num].pop();
	}
}

queue<integer> q;
void Bfs(const int & num)
{
	cout << num << ' ';
	bIsVisit[num] = true;
	
	while (node2[num].empty() == false)
	{
		//방문하지 않았으면 큐에 추가
		if (bIsVisit[node2[num].top()] == false)
		{
			q.push(node2[num].top());
			bIsVisit[node2[num].top()] = true;
			node2[num].pop();
		}
	}

	//이제 다음 인접 노드 방문
	while (q.empty() == false)
	{
		cout << q.front() << ' ';
		while (node2[q.front()].empty() == false && q.size() < N)
		{
			if (bIsVisit[node2[q.front()].top()] == false)
			{
				bIsVisit[node2[q.front()].top()] = true;
				q.push(node2[q.front()].top());
			}
			node2[q.front()].pop();
		}
		q.pop();
	}
}

int main()
{
	
	cin >> N >> M >> V;

	integer a, b;
	for (int i = 0; i < M; ++i)
	{
		cin >> a >> b;
		node[a].push(b);
		node[b].push(a);
		node2[a].push(b);
		node2[b].push(a);
	}

	Dfs(V);
	memset(bIsVisit, 0, MAX_NODE * sizeof(bool));
	cout << "\n";
	Bfs(V);

	return 0;
}

---

||사고 과정

2번째 풀어보는 그래프문제여서 좀 익힐겸 직접 구현해 풀었는데, 그래서 그런지 쓸때없는 부분이 너무 많다ㅋㅋ

순서에 상관 없이 탐색해 나가는게 아니라 인접노드의 오름차순으로 탐색을 하는거라

input을 모두 받고 퀵정렬로 한번 정렬할것인지, 우선순위큐(pq)로 그냥 넣기고 빼면서 사용할것인지 생각했었다.

 

그래서 따로 정렬부분을 쓰지 않으려 pq를 사용했는데 생각해보니

데이터의 변동이 있는편이 아니라 굳이 썼어야 했나 싶다, 속도도 뒤쳐지고ㅠ

 

데이터 변동없이 한번만 딱 정렬하면 되는 경우에는 pq보단 퀵을 사용하자..!

---

||사용 기법

• DFS
• BFS
• 우선순위 큐

---

||나아 진것

• 그래도 점점 여러가지 방법으로 풀어보려고 하는거 같다.