[백준 1260] DFS와 BFS (C++/Python)

C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX_NUM 1001
using namespace std;

bool visited[MAX_NUM];

void DFS(int cur, vector<vector<int>>& v) {
	cout << cur << " ";

	for (int i = 0; i < v[cur].size(); i++) {
		int next = v[cur][i];
					
		if (!visited[next]) {
			visited[next] = true;
			DFS(next, v);
		}
	}
}

void BFS(int n, vector<vector<int>> &v) {
	queue<int> q;
	visited[n] = true;
	q.push(n);

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		cout << cur << " ";

		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i];

			if (!visited[next]) {
				visited[next] = true;
				q.push(next);
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, s;
	cin >> n >> m >> s;

	vector<vector<int>> v(n+1);

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

		v[x].push_back(y);
		v[y].push_back(x);
	}

	for (int i = 0; i < v.size(); i++)
		sort(v[i].begin(), v[i].end());

	visited[s] = true;
	DFS(s, v);

	fill(visited, visited + MAX_NUM, false);
	cout << "\n";
	
	BFS(s, v);

	return 0;
}

 

 

 

Python)

import sys
from collections import deque

read = sys.stdin.readline

n, m, v = map(int, read().rstrip().split())
arr = [[] for _ in range(n+1)]
visited = [False] * (n+1)
    
dfs_ans = []
bfs_ans = []

def DFS(cur):
    dfs_ans.append(cur)

    for next in arr[cur]:
        if not visited[next]:
            visited[next] = True
            DFS(next)

def BFS(start):
    visited = [False] * (n+1)
    q = deque()

    visited[start] = True
    q.append(start)
    
    while q:
        cur = q.popleft()
        bfs_ans.append(cur)

        for next in arr[cur]:
            if not visited[next]:
                visited[next] = True
                q.append(next)


for _ in range(m):
    x, y = map(int, read().rstrip().split())
    arr[x].append(y)
    arr[y].append(x)

# 정점 작은 순서대로 방문
for ele in arr:
    ele.sort()

# DFS
visited[v] = True
DFS(v)

# BFS
BFS(v)

print(*dfs_ans)
print(*bfs_ans)