1260 DFS와 BFS

백준 1260 DFS와 BFS : https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

[개념(간단하게 정리)]

출처 : https://bit.ly/3tzayLq

깊이 우선 탐색(DFS, Depth First Search) : 

탐색 방법 : 현재 노드에서 분기를 완벽하게 탐색 후 다음 분기로 넘어감의 반복

• 스택으로 구현 가능

 

너비 우선 탐색(BFS, Breadth First Search)

탐색 방법 : 현재 노드에서 연결된 노드를 모두 방문하면 다음 노드로 넘어가 또 그노드에 연결된 노드를 모두 방문의 반복

• 큐로 구현 가능
• 특정 노드 사이의 최단 경로를 확인하고 싶을 때 사용
  • BFS를 사용해야 모든 노드를 방문 안해도 됨, DFS의 경우 모든 노드를 방문해야함.

 

[문제 풀이 전]

DFS 함수

• 재귀함수로 구현

BFS 함수

• 반복문 + 큐 사용

 

[문제풀이]

#include<iostream>
#include<queue>
using namespace std;
#define MAX 1001

int N, M, V;
int map[MAX][MAX] = {};
bool check[MAX] = {};

void DFS(int v) {
	cout << v << " ";
	check[v] = true;

	for (int i = 1; i <= N; i++) {
		if (map[i][v] == 1 && !check[i]) DFS(i);
	}
}

void BFS() {
	queue<int> q;
	q.push(V);
	cout << V << " ";
	check[V] = true;

	while (!q.empty())
	{
		int v = q.front(); q.pop();
		for (int i = 1; i <= N; i++) {
			if (map[i][v] == 1 && !check[i]) {
				q.push(i);
				cout << i << " ";
				check[i] = true;
			}
		}
	}
	
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> V;
	for (int i = 1; i <= M; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		map[v1][v2] = 1;
		map[v2][v1] = 1;
	}

	DFS(V);
	for (int i = 1; i <= N; i++) {
		check[i] = false;
	}
	cout << "\n";
	BFS();

	return 0;

}

bool check[MAX]		해당 노드를 방문했는지 확인하는 배열
DFS(int v)	int v		현재 기준이 되는 노드, 해당 노드의 분기를 탐색 후 다음 분기로 넘어감.
	① 현재 기준이 되는 노드를 출력 및 check ② 배열을 탐색하며 연결된 노드가 있으면 DFS(i)로 깊이 우선 탐색

BFS()	queue<int> q		너비 우선 탐색을 위해 방문한 노드를 저장하는 큐
	int v		현재 기준이 되는 노드, 해당 노드에 연결된 노드들을 모두 확인
	① 입력받은 V값 q에 저장 및 출력 ② 큐에 저장된 값을 빼며 while 반복문 진행, 더이상 없을 경우 탈출 ③ for 반복문에서 v와 연결된 노드를 모두 확인 및 출력 후 큐에 방문 노드 저장

[comment]

DFS, BFS는 이미 배운거라 쉽게 구현함, 또 문제가 쉬어서 단순한 스택 큐 문제로 보고 해결할 수 있었다.

과거 배운 내용 복습하는 느낌으로 풀어봤다.