[DFS,BFS] 백준 1260번 BFS와 DFS(C++)

 

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

BFS와 DFS라는 개념에 대해서 아는가?

 

예제를 통한 예시를 보여주겠다

 

먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다

 

대략 이렇게 그려져 있다

 

그리고 문제내부에 보면 정점 번호가 작은것을 먼저 방문한다고 했다

 

그리고 bfs와 dfs에 대한 간략한 설명을 하자면

 

bfs : 

현재 노드에서 방문할 수 있는 점을 먼저 모두 방문, 그 이후 연결된 점을 또 시작으로 방문가능한 모든 점을 방문(작은순서로)

 

dfS:

현재 노드에서 가장 깊에 들어갈 수 있는 점을 방문, (한 방향으로 끝까지) 막히면 되돌아와서 다른길을 탐색

 

그림으로 bfs를 먼저 설명해 주겠다

입력상 1을 먼저 탐색하게 되니

당연히 1이 먼저 들어온다

 

그 이후 1과 맞닿은 모든 노드들을 방문한다

(bfs니까)

작은 번호대로 나아가니까 1,2,3,4일 것이다.

그리고 모든 닿은 노드들을 보았으니 2번으로 넘어간다 ( 닿은 노드 중 가장 작은 )

 

그리고 이제 1,3,4로 찾는 것인데, 이미 한번 방문한 노드이므로 2번은 패스한다..

 

이걸 3번과 4번도 반복한다

 

그렇다면 1,2,3,4라는 순서가 나오게 되며

 

보통 bfs는 queue통해 구현하게 된다

(fifo 순서대로 출력해야 하니까)

 

그 다음은 dfs다

 

가장 깊은곳을 찾아가야 한다는 것

 

 

먼저 1번을 보자

1번과 닿아있는 노드중 가장 작은 노드인 2번으로 먼저 직행한다

 

그 후 2번과 닿아있는 노드중 가장 작은값을 찾아가면 되는데 1은 이미 방문한 노드이니 4번으로 간다

 

이제 4번에서 3번으로 간다 

 

무슨뜻인지 알겠는가?

 

가장 깊은곳으로 간다는 것이다!

 

이것은 재귀함수로 구현하면된다

 

#include <iostream>

#include <iostream>

#include <vector>

#include <string.h>

#include <queue>

#include <algorithm>

using namespace std;

int n, m, l;

vector<int> v[10002];

vector<int> a;

vector<int> b;

void bfs(int temp);

void dfs(int x);

bool visited[1002];

int main()

{

    cin >> n >> m >> l;

    for (int i = 0; i < m; i++)

    {

        int x, y;

        cin >> x >> y;

        v[x].push_back(y);

        v[y].push_back(x);

    }

    for (int i = 1; i <= n; i++)

    {

        sort(v[i].begin(), v[i].end());

    }

    bfs(l);

    memset(visited, false, sizeof(visited));

    dfs(l);

    for (int i = 0; i < b.size(); i++)

    {

        cout << b[i] << " ";

    }

    cout << '\n';

    for (int i = 0; i < a.size(); i++)

    {

        cout << a[i] << " ";

    }

}

void bfs(int temp)

{

    queue<int> q;

    q.push(temp);

    visited[temp] = true;

    while (!q.empty())

    {

        int x = q.front();

        q.pop();

        a.push_back(x);

        for (int i = 0; i < v[x].size(); i++)

        {

            if (!visited[v[x][i]])

            {

                q.push(v[x][i]);

                visited[v[x][i]] = true;

            }

        }

    }

}

void dfs(int x)

{

    visited[x] = true;

    b.push_back(x);

    for (int i = 0; i < v[x].size(); i++)

    {

        if (!visited[v[x][i]])

            dfs(v[x][i]);

    }

}

 

bfs 함수를 볼까?

 

bfs 함수에서 각 첫번째 값에 닿아있는 모든값을 순서대로 넣어줘야되므로 while 문 내부의 for문에서 진행하고 

이제 그 다음값을 시작으로 또 진행하면 된다

이떄 visited를 사용하여 이미 방문한 값은 다시 시작하지 않는다.

 

그렇게 q안에 값을 모두 넣은 후, 이제 새로 들어가는 값이 없게 되면? 끝

 

dfs는 더 간단하다 

 

당장 들어가면 true로 해주고, 닿아있는 값들에 대해 모두 재귀함수를 때려주면 된다

 

그렇다면 쑥쑥 깊은곳으로 들어가게 되며 만약 끝일경우 backtraking을 통해 나올 것이다.

 

 

※참고한 글 

https://hagisilecoding.tistory.com/16

백준 1260 DFS와 BFS C++ [컴공과고씨]

어려웠어요 저한텐 ㅠㅠ