[백준/C++] 1260번 DFS와 BFS / 코딩테스트/ 알고리즘

백준 1260번 BFS와 DFS

 

---

BFS와 DFS 풀이

이 문제는 생각보다 까다로울 수 있는데, 일반적인 BFS와 DFS 구현에서 추가로 조건이 다음과 같이 붙는다.

 

조건 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다.

조건 2. DFS와 BFS 동시에 구현하기 

조건 3. 들어간 순서대로 출력하기

 

BFS

void Bfs(int start) {
	Q.push(start);
	vis_b[start] = 1;
	cout << start << " ";
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();

		sort(vec[cur].begin(), vec[cur].end());

		for (int i = 0; i < vec[cur].size(); i++) {
			if (vis_b[vec[cur][i]] == 1) continue;
			Q.push(vec[cur][i]);
			vis_b[vec[cur][i]] = 1;
			cout << vec[cur][i] << " ";
		}
	}
	
}

 

먼저, BFS를 보면 일반적인 구현방식과 동일한데 중간에 sort 함수가 보일 것이다. 간선의 개수가 최대 10,000개까지 가능해서 처음에 이중 for문을 시도했다가 시간초과가 뜨는 쓴 맛을 봤다... ㅋㅋ 이중 for문에 시간복잡도는 O(n^2) 이고 내가 현재 쓴 sort는 시간복잡도가 O(nlogn)이다. 따라서 만개의 테스트 케이스를 돌릴려면 sort를 쓰는게 유리하다.

 

DFS

void Dfs(int start) {
	S.push(start);
	vis_d[start] = 1;
	//cout << start << " ";

	while (!S.empty()) {
		int cur = S.top(); S.pop();
		if (pri[cur] == 0) {
			cout << cur << " ";
			pri[cur] = 1;
		}
		sort(vec[cur].rbegin(), vec[cur].rend());


		for (int i = 0; i < vec[cur].size(); i++) {
			if (vis_d[vec[cur][i]] == 1 && pri[vec[cur][i]]) continue;
			S.push(vec[cur][i]);
			vis_d[vec[cur][i]] = 1;
			
		}
	}
	cout << '\n';
}

 

DFS에서는 살짝 까다로운게 Stack을 사용하기 때문에 FILO(first in last out)을 감안하고 전개해야한다. 

입력 조건에 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 라고 되어있다.

즉, 한 노드에 여러개가 연결되어있을 때 제일 작은 번호를 가진 노드를 마지막에 넣어줘야한다.

sort(vec[cur].rbegin(), vec[cur].rend());

따라서, 같은 노드에 들어있는 벡터들의 원소들을 내림차순으로 정렬해주면 해결될 수 있다.

 

여기서 문제..가 또 하나 발생한다.

 

바로 뭐냐면, 상위 노드 1을 기준으로 입력에 2,3,4가 들어왔다고 가정하자. 그렇다면 제일 먼저 탐색을 2로 할 것이다. 2에 원소에는 4가 있다. 그러면 출력을 1 - 2- 4 - 3 순으로 해줘야하는데, 일반적인 DFS 는 이미 4를 탐색했다고 가정할 것이다. 그러면 2에 들어갔을 때 어? 4가 이미 들어있는데 그럼 패스~ 하고 넘어갈 수 있다. 그걸 방지하기 위해 나는 bool pri[1001]을 정의해줘서 이거 프린트 해줬어? 라는 체크 변수를 하나 더 만들어줬다.

if (vis_d[vec[cur][i]] == 1 && pri[vec[cur][i]]) continue;

 

그래서 방문할때 조건문이 하나 추가로 pri[vec[cur][i]] 가 붙는 것이다!!

 

 

---

BFS . DFS 최종 코드 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;
vector<int> vec[1001];
queue<int> Q;
stack<int> S;
bool vis_b[1001];
bool vis_d[1001];
bool pri[1001];

void Bfs(int start) {
	Q.push(start);
	vis_b[start] = 1;
	cout << start << " ";
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();

		sort(vec[cur].begin(), vec[cur].end());

		for (int i = 0; i < vec[cur].size(); i++) {
			if (vis_b[vec[cur][i]] == 1) continue;
			Q.push(vec[cur][i]);
			vis_b[vec[cur][i]] = 1;
			cout << vec[cur][i] << " ";
		}
	}
	
}

void Dfs(int start) {
	S.push(start);
	vis_d[start] = 1;
	cout << start << " ";
	
	//vector<int> vecc;

	while (!S.empty()) {
		int cur = S.top(); S.pop();
		if (pri[cur] == 0) {
			cout << cur << " ";
			pri[cur] = 1;
		}
		sort(vec[cur].rbegin(), vec[cur].rend());

		//vecc.push_back(vec[cur][0]);

		for (int i = 0; i < vec[cur].size(); i++) {
			if (vis_d[vec[cur][i]] == 1 && pri[vec[cur][i]]) continue;
			S.push(vec[cur][i]);
			vis_d[vec[cur][i]] = 1;
			
		}
	}
	cout << '\n';
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,v;
	cin >> n >> m >> v;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;

		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	vis_b[v] = 1;
	vis_d[v] = 1;

	Dfs(v);
	Bfs(v);
	

}