Baekjoon1260-DFS와 BFS

백준 사이트 1260- DFS와 BFS 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

기초 BFS, DFS 문제입니다.

---

4. 생각한 것들

• python으로 고치기

---

5. code

c++

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

void dfs(int start, vector<int> graph[], bool check[])
{
	check[start] = true;
	printf("%d ", start);

	for (int i = 0; i < graph[start].size(); ++i)
	{
		int next = graph[start][i];
		if (check[next] == false)
			dfs(next, graph, check);
	}
}
void bfs(int start, vector<int> graph[], bool check[])
{
	queue<int>q;

	q.push(start);
	check[start] = true;

	while (!q.empty())
	{
		int tmp = q.front();
		q.pop();
		printf("%d ", tmp);
		for (int i = 0; i < graph[tmp].size(); ++i)
		{
			if (check[graph[tmp][i]] == false)
			{
				q.push(graph[tmp][i]);
				check[graph[tmp][i]] = true;
			}
		}
	}
}
int main()
{
	int n, m, start;
	cin >> n >> m >> start;
	vector<int>* graph=new vector<int>[n+1];
	bool* check = new bool[n + 1];
	fill(check, check + n + 1, false);
	int u, v;

	for (int i = 0; i < m; ++i)
	{
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i)
		sort(graph[i].begin(), graph[i].end());
	dfs(start, graph, check);
	fill(check, check + n + 1, false);
	puts("");
	bfs(start, graph, check);
	
	for (int i = 0; i < graph[i].size(); ++i)
		graph[i].clear();
	graph->clear();

	return 0;
}

python

import sys
#BFS
from collections import deque

def DFS(graph,root,visited):
    visited[root] = 1
    print(root)
    
    for i in range(len(graph[root])):
        next = graph[root][i]
        if(graph[root][i]!= 0 and visited[next]==0):
            DFS(graph,next,visited)

def BFS(graph, root,visited):
    queue = deque([root])
    visited[root]=1
    while queue:
        n = queue.popleft()
        print(n)
        for i in range (len(graph[n])):
            if(graph[n][i] != 0 and visited[graph[n][i]]==0): 
                queue.append(graph[n][i])
                visited[graph[n][i]]=1


n,m,v = map(int,input().split())
graph = [[0]* (n+1) for i in range(n+1)]
visited = [0] * (n+1) 
for i in range (0,m):
    first,second = map(int,input().split())
    graph[first][second] = second
    graph[second][first]= first

DFS(graph,v,visited)
for i in range (0,n+1):
    visited[i]=0
BFS(graph,v,visited)

---

6. 후기

python으로 처음바꿔봤는데

메모리랑 시간 차이가 너무 많이 난다.. 왜일까..

50b8024c45aaee6221eae1385dddd61fc2c7adea