백준 1260 : DFS와 BFS ★

★★★★☆

DFS와 BFS가 뭔지도 잘 모르는 상태에서 시작했더니 체감 난이도가 높았다..

문제

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

개념

(열혈 자료구조 책 참고. 내가 이해한대로 정리하기)

1. DFS
   1) 깊이우선탐색. 한 길로 깊게 파고들어간다.
   2) 어떠한 우선순위에 따라(이 문제에서는 숫자가 더 작은 정점) 한 정점으로만 나아간다.
   ※ 어떤 길로 못 갈 일은 걱정할 필요 없다.
   3) 막다른 길에 도착했다면 호출한 정점으로 복귀
   (함수를 정의해야하는 이유. 호출한 코드의 다음 코드가 이어서 실행될 수 있으므로.)
   4) 막다른 길 : 연결된 정점들이 모두 방문했던 정점인 경우
2. BFS
   1) 너비우선탐색. 자신과 연결된 정점을 모두 기록한다.
   2) 1차적으로 연결되어있는 정점들을 먼저 한번 훑고 다음으로 나아가야 한다.
   따라서, queue와 같은 자료구조에 정점들을 담아두었다가, 모두 훑고나면 하나씩 꺼내면서 이어서 진행한다. (DFS와의 차이점)
   3) 막다른 길 : queue에 더이상 정점이 없는 경우

나의 풀이

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

int n, m, v;
bool graph[MAXSIZE][MAXSIZE];
bool visit[MAXSIZE];
queue<int> dfsqueue;

void resetvisit() {
	for (int i = 0; i < MAXSIZE; i++) {
		visit[i] = false;
	}
}

void dfs(int p) {//DFS, 깊이우선탐색
	visit[p] = true;
	cout << p << " ";

	for (int i = 1; i <=n; i++) {
		if (graph[p][i]&&!visit[i]) { //연결되어 있고, 방문하지 않았다면 다음으로
			visit[i] = true; //방문 기록
			dfs(i); 
		}
	}
	return; //방문할 노드가 없다면 리턴
}

void bfs(int p) {//BFS, 너비우선탐색
	dfsqueue.push(p); //현재 정점을 실행하기 위해 push해줌
	visit[p] = true;
	cout << p << " ";

	while (!dfsqueue.empty()) {
		int tem = dfsqueue.front();
		dfsqueue.pop();
		for (int i = 1; i <= n; i++) {
			if (graph[tem][i] && !visit[i]) { //연결되어 있고, 방문하지 않았다면 다음으로
				visit[i] = true; //방문 기록
				dfsqueue.push(i); //큐에 정점 기록하기
				cout << i << " ";
			}
		}
	}
	return;
}

int main() {
	
	cin >> n >> m >> v;

	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;

		graph[x][y] = true;
		graph[y][x] = true;
	}

	resetvisit();
	dfs(v);
	cout << "\n";

	resetvisit();
	bfs(v);
	cout << "\n";
	return 0;
}

전역변수를 사용해서 풀었지만, 함수의 매개변수로 그래프와 배열을 전달하는 방법도 있다.
그래프는 class를 사용해서 구현해보기도 하였지만, 코드가 무거워질뿐 큰 이점은 없어서 2차원배열로 변경했다.