[백준 1260번 - DFS와 BFS] C++ 풀이

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

1260번: DFS와 BFS

 

1260번: DFS와 BFS

 

해당 문제는 DFS, BFS 의 기본 알고리즘을 연습하기 딱인 문제이다.

 

이 문제를 예전에는 DFS를 재귀로 짰길래, 이번에는 스택으로 짜보았다.

 

DFS를 인접리스트로 짤 경우는 시간복잡도가 O(V+E) 이다. DFS 를 V번 호출하고, 그 안에서 해당 정점에 연결된 간선의 갯수만큼 탐색하므로, 총 V+E 이다.

반면 인접행렬로 짤 경우는 O(V^2) 이다. DFS가 V 번 호출되고, 각 호출에서 모든 정점을 다 돌면서 찾으므로 V^2 이다.

BFS 또한 같은 방식으로 계싼하여 마찬가지의 시간복잡도를 가진다.

 

완성된 코드

#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <stdio.h>

using namespace std;

bool visited[1001];
vector<int> graph[1001];
stack<int> s;
queue<int> q;

void dfs(int start) {
	s.push(start);
	visited[start] = true;
	cout << start << " ";
	while (!s.empty()) {
		int currunt = s.top();
		bool flag = false;
		for (int i = 0; i < graph[currunt].size(); ++i) {
			//cout << "\n" << "현재 노드는 " << currunt <<"이고, 인접 노드는" << graph[currunt][i] << ", " << visited[graph[currunt][i]] << endl;
			if (visited[graph[currunt][i]] != true && graph[currunt][i] != 0) {
				s.push(graph[currunt][i]);
				visited[graph[currunt][i]] = true;
				flag = true;
				cout << graph[currunt][i] << " ";
				break;
			}
		}
		if (flag == false) {
			s.pop();
		}
	}
}

void bfs(int start) {
	q.push(start);
	visited[start] = true;

	while(!q.empty()) {
		int currunt = q.front();
		cout << currunt << " ";
		q.pop();
		for (int i = 0; i < graph[currunt].size(); ++i) {
			if (visited[graph[currunt][i]] != true) {
				q.push(graph[currunt][i]);
				visited[graph[currunt][i]] = true;
			}
		}
	}
}

int main() {
	int n, m, start;
	scanf("%d %d %d", &n, &m, &start);
	memset(visited, false, n + 1);
	for(int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	for(int i = 1; i <= n; ++i) {
		sort(graph[i].begin(), graph[i].end());
	}

	dfs(start);
	memset(visited, false, n + 1);
	cout << endl;
	bfs(start);
}