[ C++ / DFS, BFS ] 백준 1260 - DFS와 BFS

📄 문제

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

⌨ 입력

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

💻 출력

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

📌 예제 1

[ Input ]

4 5 1
1 2
1 3
1 4
2 4
3 4

[ Output ]

1 2 4 3
1 2 3 4

📌 예제 2

[ Input ]

5 5 3
5 4
5 2
1 2
3 4
3 1

[ Output ]

3 1 2 5 4
3 1 4 2 5

📌 예제 3

[ Input ]

1000 1 1000
999 1000

[ Output ]

1000 999
1000 999

---

📝 풀이

핵심

• DFS, BFS의 각 특성 이용이 핵심!

📌 정점들의 인접 정점 리스트를 만들어 준다.

📌 이미 방문한 정점은 카운트 할 필요 없으므로 각 정점의 방문 상태를 나타내는 방문 배열을 만들어 준다.

📌 DFS 함수 구현

• 재귀 함수로 구현

📌 BFS 함수 구현

• queue 이용

📌 방문할 수 있는 정점이 여러개인 경우 가장 작은 값 부터 방문 해야 하므로 sort()함수로 정렬 필요.

소스 코드

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

using namespace std;

int iN = 0;
int iM = 0;
int iV = 0;

vector<vector<int>> vecAdjacencyList;
vector<bool> vecVisited;
queue<int> q;

void DFS(int iIndex)
{
    if (true == vecVisited[iIndex])
        return;
    else
    {
        vecVisited[iIndex] = true;
        cout << iIndex << ' ';
    }

    int iSize = vecAdjacencyList[iIndex].size();

    for (int i = 0; i < iSize; ++i)
        DFS(vecAdjacencyList[iIndex][i]);
}

void BFS(int iIndex)
{
    if (true == vecVisited[iIndex])
    {
        q.pop();
        return;
    }
    else
    {
        vecVisited[iIndex] = true;

        int iSize = vecAdjacencyList[iIndex].size();

        for (int i = 0; i < iSize; ++i)
            q.emplace(vecAdjacencyList[iIndex][i]);

        q.pop();
        cout << iIndex << ' ';
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> iN >> iM >> iV;

    vecAdjacencyList.resize(iN + 1);
    vecVisited = vector<bool>(iN + 1, false);

    for (int i = 0; i < iM; ++i)
    {
        int iSvertex = 0;
        int iEvertex = 0;

        cin >> iSvertex >> iEvertex;

        vecAdjacencyList[iSvertex].emplace_back(iEvertex);
        vecAdjacencyList[iEvertex].emplace_back(iSvertex);
    }

    int iSize = vecAdjacencyList.size();

    for (int i = 0; i < iSize; ++i)
    {
        sort(vecAdjacencyList[i].begin(), vecAdjacencyList[i].end());
    }

    DFS(iV);
    cout << '\n';

    vecVisited = vector<bool>(iN + 1, false);

    q.emplace(iV);

    while (false == q.empty())
    {
        BFS(q.front());
    }

    return 0;
}

---

༼ つ ◕_◕ ༽つ 여담

😁 DFS, BFS의 기본적인 특성을 이해했는지 물어보는 문제!
DFS문제를 몇 문제 정도 풀어보고 이제 BFS 문제를 풀어보려하니 나온 기본적인 문제..
DFS함수는 풀어본 경험을 토대로 금방 만들었는데 BFS는 좀 고민 했던 것 같다!
자꾸 DFS처럼 재귀로 풀어버리려고.....