[C++] 백준 1260번: DFS와 BFS

문제

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

문제는 간단하게 DFS와 BFS를 구현하는 문제다. 

당연히 DFS와 BFS의 개념을 알아야 풀 수 있다. 

 

풀이

 

노드와 간선으로 이루어진 그래프를 표현하기 위해 2차원 배열을 선언해주었다. 

#define MAX 1001
int arr[MAX][MAX];

 

입력 받은 그래프의 노드 a와 b의 연결을 아래처럼 표현해주었다. 

std::cin >> a >> b;
arr[a][b] = arr[b][a] = true;

 

이미 방문한 노드를 재방문 여부를 확인할 bool 타입 배열도 선언해주었다. 

bool visited[MAX] = {false, };

 

 

DFS

 

DFS는 시작 노드 (v)로부터 가장 인접한 노드를 찾는 탐색이 반복되기 때문에 재귀함수를 이용하여 문제를 풀었다. 

이 때 노드가 이어져 있는 곳만 가야 하므로 arr[v][i] 조건과 노드 재방문을 막기 위해서 visited[i] == false 조건을 달아주었다.

void DFS(int v)
{
    visited[v] = true;
    std::cout << v << " ";
    
    for(int i =1; i<=N; ++i)
    {
        if(arr[v][i] && visited[i] == false)
        {
            DFS(i); // 재귀 함수
        }
    }
}

 

 

BFS

 

BFS는 시작 노드 (v)의 인접한 노드들을 모두 방문한 후, 방문 했던 노드들 중 가장 인접한 노드를 시작으로 재탐색을 하는 방식이다. 

즉, BFS는 방문했던 노드들을 저장해야 하며, 가장 먼저 방문 했던 노드부터 재탐색을 시작해야 한다. 

 

FIFO를 위해 queue를 이용해 풀었다.

 

void BFS(int v)
{
    bool visited[MAX] = {false, };
    std::queue<int> q;
    
    q.push(v);
    visited[v] = true;
    std::cout << v << " ";
    
    while(!q.empty())
    {
    	v = q.front(); q.pop();
        
	    for(int i = 1; i <= N; ++i)
	    {	
	        if(arr[v][i] && visited[i] == false)
	        {
	        	q.push(i);
	            visited[i] = true;
	            std::cout << i << " ";
	        }
		 }
    }
    
}

소스

#include <iostream>
#include <queue>
#define MAX 1001
bool visited[MAX] = {false, };
int arr[MAX][MAX];
int N;
 
 
 
void BFS(int v)
{
    bool visited[MAX] = {false, };
    std::queue<int> q;
    
    q.push(v);
    visited[v] = true;
    std::cout << v << " ";
    
    while(!q.empty())
    {
        v = q.front(); q.pop();
        
        for(int i = 1; i <= N; ++i)
        {    
            if(arr[v][i] && visited[i] == false)
            {
                q.push(i);
                visited[i] = true;
                std::cout << i << " ";
            }
         }
    }
    
 
}
 
void DFS(int v)
{
    visited[v] = true;
    std::cout << v << " ";
    
    for(int i =1; i<=N; ++i)
    {
        if(arr[v][i] && visited[i] == false)
        {
            DFS(i);
        }
    }
}
 
int main()
{
    int a =0, b =0;
    int M =0, V = 0;
    std::cin >> N >> M >> V;
    
    while(M--) // 간선 개수만큼 읽어들이면 됨
    {
        std::cin >> a >> b;
        arr[a][b] = arr[b][a] = true;
    }
    
    DFS(V);
 
      for(int i =0; i<=N; ++i)
    {
      visited[i] = false;
    }
    std::cout << "\n";
    
    BFS(V);
    
        
    return 0;
}