[백준/Baekjoon] 1260 DFS와 BFS C++ :: DFS / BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

1. Logic

> 기본 DFS / BFS문제

 

Depth First Search(DFS)

- 재귀를 사용하며 자기 자신을 호출하여 깊게 들어가며 노드를 확인하며 검색한다.

- DFS를 구현할 때 주의해야할 점은 탐색한 경우 방문처리를 하여 다시 들어가지 않도록 하여 무한루프에 빠지는 것을 필히 방지하여야 한다. 기저조건을 잘 파악하고 방문처리를 해야한다.

 

Breadth First Seach(BFS)

- DFS는 한 노드에 이어진 다른 노드를 깊게 들어가는 방식이라면 BFS깊이보단 넓게, 즉 자기 자신 노드와 인접한 노드를 먼저 탐색하는 Search 방법이다.

- BFS 또한 방문여부를 반드시 검사해야하며, 검사하지 않을 경우 무한루프에 빠지게 된다.

- BFS는 방문한 노드를 차례대로 검사할 수 있게 선입선출(FIFO)의 성질을 가진 queue / priority_queue를 사용하여 구현한다.

 

---

2. Code

#include<bits/stdc++.h>
using namespace std;

int vertex, edge, start_point;
bool visited_DFS[1001];
bool visited_BFS[1001];
vector<int> v[1001];

void DFS(int start_point)
{
	cout << start_point << " ";
	visited_DFS[start_point] = true;
	
	for(int node : v[start_point])
	{
		if(!visited_DFS[node])
		{
			DFS(node);
		}
	}
}

void BFS(int start_point)
{
	queue<int> q;
	q.push(start_point);
	visited_BFS[start_point] = true;
	
	while(!q.empty())
	{
		int cur_node = q.front();
		q.pop();
		cout << cur_node << " ";
		for(int node : v[cur_node])
		{
			if(!visited_BFS[node])
			{
				visited_BFS[node] = true;
				q.push(node);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> vertex >> edge >> start_point;
	
	for(int i = 1; i <= edge; i++)
	{
		int start, dest;
		cin >> start >> dest;
		v[start].push_back(dest);
		v[dest].push_back(start);
	}
	
	for(int i = 1; i <= vertex; i++)
	{
		sort(v[i].begin(), v[i].end());
	}
	
	DFS(start_point);
	cout << "\n";
	BFS(start_point);
	return 0;
}

 

 

---

 

 

3. Feedback

- 항상 방문처리를 꼼꼼하게 하고 기저조건을 잘 세우며 continue할 조건의 순서또한 작 확인해야 한다.