[BOJ 1260번](DFS/BFS) DFS와 BFS (C++)

DFS와 BFS (실버 II)

문제

전체 문제 보기

1260번: DFS와 BFS

접근법

이 문제는 DFS / BFS 유형의 입문 문제이다. 주어진 도시와 간선 정보를 바탕으로 모든 도시를 DFS로 한번 출력하고 BFS로 한번 출력하는 문제이다. 때문에 가장 정석의 DFS와 BFS를 각각 구현하면 된다. 바로 구현을 시작한다.

주의사항

필자는 처음 코드를 제출 했을 때 87% 에서 런타임 에러가 발생했었다. 이유는 출발 노드에 간선이 연결되어 있지 않은 경우를 고려하지 않아서였다. 만약 이러한 오류를 겪는 다면 아래의 테스트 케이스를 사용해보자.

입력
100 1 1
2 3

출력
1
1

자료구조 선택

먼저 각 정점에 대한 정보를 담을 Node 구조체를 다음과 같이 선언한다. 

struct Node {
    Node(int num)       // 모든 노드는 할당된 숫자가 있어야한다.
        :mNum(num)
        ,mVisited(false)   // 방문 정보를 false로 초기화
    {}

    vector<Node*> mAdjacent;    // 인접 노드에 대한 정보
    int mNum;                   // 노드에 할당된 숫자
    bool mVisited;              // 방문 정보
};

문제에서 정점의 정보를 숫자로 주지만 우리는 Node 구조체의 인스턴스를 생성해서 활용하고자 한다. 때문에 1이라는 숫자로 1에 해당하는 Node 인스턴스의 주소에 접근할 수 있어야 한다. 이를 위해서 main함수에 아래와 같이 해시테이블을 저장해 두고, 이를 활용하여 정점의 정보를 입력받자.

unordered_map<int, Node*> nodes;

cin >> N >> M >> V;

// (1 ~ N 까지의 정점을 생성)
while (N--)
{
    nodes[N + 1] = new Node(N + 1);
}

다음은 간선에 대한 정보를 입력받는다. 문제에서 명확히 언급된 것은 아니지만 방향이 없는 간선 즉, 양방향 간선으로 이루어져 있다. 따라서 1 2라고 입력받았다면, 1의 인접 노드에 2를 추가하고 2의 인접 노드에 1을 추가하자.

while (M--)
{
    int A, B;
    cin >> A >> B;

    nodes[A]->mAdjacent.emplace_back(nodes[B]);
    nodes[B]->mAdjacent.emplace_back(nodes[A]);
}

하나의 노드에 인접한 노드가 여러 개일 경우 작은 숫자부터 출력하는 것이 문제의 요구사항이다. 때문에 모든 노드에 대해서 인접 노드 벡터를 오름차순으로 정렬하자. 벡터의 자료형이 Node*이기 때문에 조건자를 우리가 만들어줘야 한다. sort함수의 3번째 인자(조건자)에 람다식을 사용하여 노드가 노드의 숫자를 기준으로 오름차순 정렬될 수 있도록 구현하였다.

// 작은 수 부터 출력하기 위해서 인접노드 배열을 오름차순으로 정렬
for (auto node : nodes)
{
    sort(node.second->mAdjacent.begin(), node.second->mAdjacent.end(),
        [](Node* left, Node* right) -> bool
        {
            return left->mNum < right->mNum;
        });
}

구현

DFS와 BFS의 구현은 아래의 전체 소스코드를 참고하자. DFS는 재귀 함수를 사용하였고, BFS는 큐를 사용하여 구현하였다. 이들의 구현 방법에 대한 설명은 이 글을 참고하자.

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

#define endl '\n'
using namespace std;

struct Node {
    Node(int num)       // 모든 노드는 할당된 숫자가 있어야한다.
        :mNum(num)
        ,mVisited(false)   // 방문 정보를 false로 초기화
    {}

    vector<Node*> mAdjacent;    // 인접 노드에 대한 정보
    int mNum;                   // 노드에 할당된 숫자
    bool mVisited;              // 방문 정보
};

void DFS(Node* begin)
{
    begin->mVisited = true;
    cout << begin->mNum << " ";
    for (auto adj : begin->mAdjacent)
    {
        if (adj->mVisited == false)
        {
            DFS(adj);
        }
    }
}
void BFS(Node* begin)
{
    queue<Node*> q;
    q.push(begin);
    begin->mVisited = true;

    do {
        Node* cur = q.front();
        q.pop();
        cout << cur->mNum << " ";

        for (auto adj : cur->mAdjacent)
        {
            if (adj->mVisited == false)
            {
                q.push(adj);
                adj->mVisited = true;
            }
        }
    } while (!q.empty());
}
int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    // N: 정점의 개수(1 ~ 1,000)
    // M: 간선의 개수(1 ~ 10,000)
    // V: 시작할 정점의 번호
    int N, M, V;

    unordered_map<int, Node*> nodes;

    cin >> N >> M >> V;

    // (1 ~ N 까지의 정점을 생성)
    while (N--)
    {
        nodes[N + 1] = new Node(N + 1);
    }

    // 각 정점에 간선의 정보를 입력. 간선은 양방향으로 연결
    while (M--)
    {
        int A, B;
        cin >> A >> B;

        nodes[A]->mAdjacent.emplace_back(nodes[B]);
        nodes[B]->mAdjacent.emplace_back(nodes[A]);
    }

    // 작은 수 부터 출력하기 위해서 인접노드 배열을 오름차순으로 정렬
    for (auto node : nodes)
    {
        sort(node.second->mAdjacent.begin(), node.second->mAdjacent.end(),
            [](Node* left, Node* right) -> bool
            {
                return left->mNum < right->mNum;
            });
    }

    // DFS에 시작 노드를 전달
    DFS(nodes[V]);

    cout << endl;

    // 방문 기록을 모두 초기화
    for (auto node : nodes) 
        node.second->mVisited = false;

    // BFS에 시작 노드를 전달
    BFS(nodes[V]);

    // 동적할당 노드 모두 삭제
    for (auto node : nodes)
    {
        delete node.second;
    }

    return 0;
}