백준 1260 -DFS와 BFS

문제 설명

 

 

=> DFS와 BFS를 사용할 줄 아는지 묻는 문제였습니다. 

=> 기본적으로 입력을 받을때 인접 행렬, 인접 리스트, 간선 리스트를 만들어두면 편합니다.

=> DFS와 BFS code 역시 형식이 정해져있으므로, 이해와 함께 암기해두시면 편리합니다. 

 

=> DFS와 BFS에 대한 설명은 생략하겠습니다.

=> DFS : 깊이를 끝까지 따라가며 탐색하는 방법 ( stack을 사용하지만, 코드에서는 재귀를 통해 구현 가능)

=> BFS : 너비를 우선시하면 탐색하는 방법 ( queue를 사용하여 코드로 구현 가능)

 

 

 

 

<DFS code>

void dfs(int x, int n) //x는 탐색 시작점, n은 정점의 갯수
{
    check[x]=true;
    cout<<x<<" ";
    for(int i=1; i<=n; i++)
    {
        if(arr[x][i] == true && check[i] ==false)//x, i가 연결되어있고 i를 가보지 않았던 경우
        {
            dfs(i, n);
        }
    }
}

 

 

<BFS code>

void bfs(int x, int N)
{
    queue<int> q;
    check[x] = true;
    cout << x <<" ";
    q.push(x);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i=1; i<=N; i++)
        {
            if(arr[x][i] == true && check[i] == false)
            {
                check[i] = true;
                cout << i <<" ";
                q.push(i);
            }
        }
    }
    cout <<'\n';
}

 

 

 

<code>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>


using namespace std;

#define MAX 2001

bool check[1001];//갔다온지 확인하는 행렬
bool arr[MAX][MAX]; //인접행렬
vector<int> list[MAX]; //인접리스트
vector<pair<int,int>>edges; //간선리스트

void dfs(int x, int n)
{
    check[x]=true;
    cout<<x<<" ";
    for(int i=1; i<=n; i++)
    {
        if(arr[x][i] == true && check[i] ==false)//x, i가 연결되어있고 i를 가보지 않았던 경우
        {
            dfs(i, n);
        }
    }
}

void bfs(int x, int N)
{
    queue<int> q;
    check[x] = true;
    cout << x <<" ";
    q.push(x);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i=1; i<=N; i++)
        {
            if(arr[x][i] == true && check[i] == false)
            {
                check[i] = true;
                cout << i <<" ";
                q.push(i);
            }
        }
    }
    cout <<'\n';
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N, M; //정점 개수, 간선 개수
    cin >> N >> M;
    int V; //Start Vertex
    cin >> V;
    
    
    for(int i=0; i<M; i++)
    {
        int from,to;
        cin >> from >> to;
        edges.push_back({from, to});
        edges.push_back({to, from});
        arr[from][to] = arr[to][from] = true;
        list[from].push_back(to);
        list[to].push_back(from);
    }
    
    
    //dfs 시작
    dfs(V, N);
    cout <<'\n';
    
    fill_n(check, 1001, false); //dfs가 끝났으므로 초기화
    
    // bfs 시작
    bfs(V,N);
    
    return 0;
}

 

 

실행 화면 1

실행 화면 2