백준 1260: DFS와 BFS (Python, C++)

3년 전에 C++로 풀었던 문제들을 파이썬으로 다시 풀어보았다.

 

문제

1260번: DFS와 BFS

정점의 개수(N), 간선의 개수(M), 시작정점(V)을 입력받고 간선의 수만큼 연결된 정점들의 번호를 입력받아 

시작정점부터 각각 DFS, BFS로 수행한 결과를 출력하면 된다.

 

DFS는 재귀함수로, BFS는 큐를 사용해 풀었다. 

 

풀이1 (Python)

from collections import deque

def dfs(v):
    dv[v]=1
    print(v,end=' ')
    for i in range(1, n+1):
        if dv[i]==0 and g[v][i]==1:
            dfs(i)

if __name__ == '__main__':
    n,m,v=map(int,input().split())
    g = [[0]*(n+1) for _ in range(n+1)]
    dv=[0]*(n+1) #dfs visit
    bv=[0]*(n+1) #bfs visit
    q = deque()

    for _ in range(m):
        x,y=map(int,input().split())
        g[x][y] = g[y][x] = 1  #간선연결

    #DFS
    dfs(v)
    print()
    #BFS
    q.append(v)
    bv[v] = 1
    while q:
        v = q.popleft()
        print(v, end=' ')
        for i in range(1, n + 1):
            if bv[i] == 0 and g[v][i] == 1:
                q.append(i)
                bv[i] = 1

 

풀이2 (C++)

//DFS와 BFS
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <memory.h>
using namespace std;

int N, M, V,V1,V2;
//stack<int>S;
queue <int> q;
int visit[1001];
int graph[1001][1001];

void dfs(int V) {
	cout << V << " ";
	for (int i = 1; i <= N; i++) {
		if (!visit[i] && graph[V][i]) {
			visit[i] = true;
			dfs(i);
		}
	}
}

void bfs(int V) {
	q.push(V);
	visit[V] = 1;
	while (!q.empty()) {
		V = q.front();
		q.pop();
		cout << V << " ";

		for(int i=1;i<=N;i++)
			if (!visit[i] && graph[V][i]) {
				visit[i] = 1;
				q.push(i);
			}
	}
}

int main() {
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++) {
		cin >> V1>> V2;
		graph[V1][V2] = 1;
		graph[V2][V1] = 1;
	}

	visit[V] = 1;
	dfs(V);
	cout << endl;

	memset(visit, false, sizeof(visit));
	bfs(V);
	cout << endl;
	
	return 0;
}

 

갈 길이 멀다... ㅎㅎ