[코딩테스트] 백준 1260 BFS/DFS - C++, PYTHON

✔문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

✔입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

✔출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

💖C++ 코드

#include <iostream>
#include <stack>
#include <queue>
using namespace std; 

void dfs(int** map , int  n,int v ) { // stack 정점이 작은것 먼저 방문
	int* visited = new int[n];
	for (int i = 0; i < n; i++)
		visited[i] = 0;
	

	stack <int> s;
	s.push(v);
	visited[v - 1] = 1; 
	cout << v << " ";

	while (!s.empty())
	{
		int current = s.top();
		for (int i = 0; i < n; i++) {
			if (i == n - 1) //경로를 모두 탐색한 경우
				s.pop();
			if (map[current - 1][i] == 1 && visited[i] == 0) {
				s.push(i + 1);
				visited[i] = 1;
				cout << i + 1 << " ";
				current = i;
				break;
			}
			/* 
			else if (current == n - 1 && !s.empty()) {
				s.pop();
			}*/
		}
	}
	
}

void bfs(int** map, int n ,int v ) { //queue
	int* visited = new int[n];
	for (int i = 0; i < n; i++)
		visited[i] = 0; 

	queue <int> q; 
	q.push(v);
	visited[v - 1] = 1; 

	while (!q.empty() )
	{
		int front = q.front();
		cout << front << " ";
		for (int i = 0; i < n; i++) {
			if (map[front - 1][i] == 1 && visited[i] == 0) {
				visited[i] = 1; 
				q.push(i +1);
			}
		}
		q.pop();
	}

}

int main() {

	int n, m, v; 
	cin >> n >> m >> v; 

	//동적 이차원 배열 선언 
	int** map = new int* [n];
	for (int i = 0; i < n; i++)
		map[i] = new int[n];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map[i][j] = 0; //초기화 
		}
	}

	for (int i = 0; i < m; i++) {
		int v1, v2; 
		cin >> v1 >> v2; 
		map[v1-1][v2-1] = 1;
		map[v2-1][v1-1] = 1;
	}

	dfs(map,n,v);
	cout << '\n';
	bfs(map,n,v);

	return 0; 
}

💖 PYTHON 코드

def bfs(list,n,v): 
    visited  = [] 
    queue = [] 
    for i in range(n): #visited 초기화 
        visited.append(0)

    #첫번째 방문 정점 추가  
    queue.append(v)
    visited[v-1] = 1
    
    #queue에 v가존재하는 동안 
    while(queue) : 
        #가장 앞에 있는 값 pop 
        front = queue.pop(0)
        print(front, end=" ")
        for i in range(n): 
            if visited[i] == 0 and list[front-1][i] == 1: 
                visited[i]=1
                queue.append(i+1)
        

    


def dfs(list,n,v): 
    visited  = [] 
    stack = [] 

    #visited 초기화 
    for i in range(n): 
        visited.append(0)

    stack.append(v)
    visited[v-1] = 1 
    print(v, end=" ")

    while(stack): 
        top = stack[-1] #뒤에서 1번째라는 의미 
        for i in range(n): 
            if i == n-1 : 
                stack.pop()
            if visited[i] == 0 and list[top-1][i] == 1: 
                visited[i] = 1
                stack.append(i+1)
                print(i+1, end=" ")
                break 

def main(): 
    n, m, v = map(int, input().split())
    list = [[0 for i in range(n+1)] for i in range(n+1)]
    for i in range(m): 
        vertex1, vertex2 = map(int, input().split())
        list[vertex1-1][vertex2-1] = 1 
        list[vertex2-1][vertex1-1] = 1  

    dfs(list,n,v)
    print('\n',end='')
    bfs(list,n,v)


if __name__ == "__main__": 
    main()