[백준] 1260번 DFS와 BFS

1260번: DFS와 BFS

파이썬과 C++로 풀어보았다.

두 언어 간 속도 차이는 엄청나다.

 

우선 파이썬으로 짠 코드이다. 그래프 클래스를 구현했다.

class Graph:
    def __init__(self, n):
        self.data = {}
        for i in range(1, n + 1):
            self.data[i] = set()
    def add_edge(self, n, m):
        self.data[n].add(m)
        self.data[m].add(n)
    def dfs(self, start):
        visited = [False] * (len(self.data) + 1)
        stack = []
        stack.append(start)
        while stack:
            cur = stack.pop()
            if not visited[cur]:
                print(cur, end=" ")
            visited[cur] = True
            temp = []
            for i in self.data[cur]:
                if not visited[i]:
                    temp.append(i)
            temp.sort()
            temp.reverse()
            stack.extend(temp)
    def bfs(self, start):
        import collections
        visited = [False] * (len(self.data) + 1)
        queue = collections.deque()
        queue.append(start)
        while queue:
            cur = queue.popleft()
            if not visited[cur]:
                print(cur, end=' ')
            visited[cur] = True
            temp = []
            for i in self.data[cur]:
                if not visited[i]:
                    temp.append(i)
            temp.sort()
            queue.extend(temp)
from sys import stdin

node_edge_start = list(map(int, stdin.readline().split()))
graph = Graph(node_edge_start[0])
li = []
for i in range(0, node_edge_start[1]):
    rawInput = list(map(int, stdin.readline().split()))
    graph.add_edge(rawInput[0], rawInput[1])
graph.dfs(node_edge_start[2])
print()
graph.bfs(node_edge_start[2])

 

C++로 짠 코드. 자식이 여러개라면 작은 수부터 방문한다는 조건이 있어서 <algorithm>의 sort() 함수를 이용해서 정렬해주었다.

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

bool cmp(int a, int b) {
	return a > b;
}

vector<int> w[1001];
int n, m, startNode;

void dfs() {
	vector<bool> visited(n + 1);
	stack<int> stack;
	stack.push(startNode);
	while (!stack.empty()) {
		int cur = stack.top();
		stack.pop();
		if (!visited[cur]) {
			cout << cur << " ";
		}
		visited[cur] = true;
		for (int v : w[cur]) {
			if (!visited[v])
				stack.push(v);
		}
	}
}
void bfs() {
	vector<bool> visited(n + 1);
	queue<int> q;
	q.push(startNode);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (!visited[cur])
			cout << cur << " ";
		visited[cur] = true;
		for (int v : w[cur]) {
			if (!visited[v]) {
				q.push(v);
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> startNode;
	int v1, v2;
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2;
		w[v1].push_back(v2);
		w[v2].push_back(v1);
	}
	for (int i = 1; i <= n; i++) {
		sort(w[i].begin(), w[i].end(), cmp);
	}
	dfs();
	cout << endl;
	for (int i = 1; i <= n; i++) {
		sort(w[i].begin(), w[i].end());
	}
	bfs();
	return 0;
}