DFS와 BFS(백준)

링크텍스트

문제 이해

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

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

나만의 이해

처음에 그래프가 어떤건지 정확하게 몰라서 문제 이해를 잘 못했다. 트리 구조로 생각하다가 예제를 보다가 이해했다.

Python

import sys
from collections import deque
def dfs(graph, v, visited):
    
    visited[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
def bfs(graph,v,visited):
    queue = deque([v])
    visited[v]= True
    while queue:
        v= queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    
n,m,v = map(int, sys.stdin.readline().split())
path =[[] for x in range(n+1)]

for i in range(m):
    a,b = map(int, sys.stdin.readline().split())
    path[a].append(b)
    path[b].append(a)

path =[sorted(x) for x in path]

visited = [False]*len(path)
dfs(path,v,visited)

print()
visited = [False]*len(path)
bfs(path,v,visited)

dfs,bfs 모두 함수로 구현해서 풀면 되는 문제인데 처음 풀면 어렵다. 일단 가능한 경로를 sorted된 상태로 만들어 주고 visited라는 boolean array 작성한뒤 각각 dfs, bfs알고리즘을 implement 해주면 된다.

C++

#include <bits/stdc++.h>
using namespace std;

void dfs(vector <int> connected[],int v, bool visited[]){
    
    visited[v] = true;
    cout<<v<<" ";
    
    for(int i : connected[v]){
    if (visited[i] == false){
        dfs(connected,i,visited);
    }
    }
    
}

void bfs(vector <int> connected[],int v, bool visited[]){
    deque<int> dp;
    dp.push_front(v);
    visited[v] = true;
    
    while (dp.size()){
        v = dp.front();
        dp.pop_front();
        cout << v<< " ";
        
        for(int i : connected[v]){
           
        if (visited[i] == false){
            dp.push_back(i);
            visited[i]=true;
}
}
}
    
}

int main()
{
    int n,m,v;
    cin >> n>>m>>v;
    
    int a,b;
    bool visited_dfs[n+1]={false};
    bool visited_bfs[n+1]={false};
    vector <int> connected[n+1];
    
    for(int i =0; i< m;i++){
        cin >> a >>b;
        connected[a].push_back(b);
        connected[b].push_back(a);
    }
    
    for(int i=1;i<=n;i++) sort(connected[i].begin(),connected[i].end(),less<>());
    
    dfs(connected,v,visited_dfs);
    cout <<'\n';
    
    bfs(connected,v,visited_bfs);
   return 0;
}