[BOJ 18352번](DFS/BFS) 특정 거리의 도시 찾기 (C++)

특정 거리의 도시 찾기 (실버II)

문제

전체 문제 보기

18352번: 특정 거리의 도시 찾기

접근법

각 도시들(Node)에 대해서 BFS 탐색을 진행한다. BFS는 출발 지점에서 거리를 한 칸씩 늘려가며 탐색하기 때문에 출발지로부터 동일한 거리에 있는 모든 노드를 출력해야 하는 이번 문제에서 높은 효율을 보일 수 있다. BFS 탐색 과정에서 탐색 수준이 목표 거리에 도달하면 목표 거리에 해당하는 도시를 모두 기록하여 출력할 수 있다. 만약 모든 탐색기간 동안 목표한 거리에 해당하는 도시가 없다면 -1을 기록하여 출력한다.

 

BFS를 활용한 길 찾기에 대해서 더 알고 싶다면 아래의 글을 참고하자.

• 그래프, DFS, BFS 기본 개념 (C 언어)

choisb/Study-DataStructure

• BFS를 통한 길찾기 예제(C++ 언어)

4장 인공지능 - ② 길 찾기 알고리즘

자료구조 선택

먼저 가장 기본이 될 자료구조 Node는 다음과 같이 선언한다. 각 Node 들은 인접한 노드에 대한 정보를 가진다.

struct Node {
    Node(int num)
        :mNum(num)
        ,mDistance(-1) // 방문하지 않은 노드의 거리는 -1로 초기화.
    {}

    vector<Node*> mAdjacents;   // 인접한 노드의 집합
    int mNum;                   // 이 Node의 도시 번호
    int mDistance;              // 출발지에서 부터 거리
};

해시 맵을 활용하면 도시의 번호로 Node*를 참조할 수 있다. 따라서 아래와 같이 모든 데이터를 입력받을 수 있다.

unordered_map<int, Node*> nodes;// 도시 번호로 Node* 를 참조할 수 있는 해시맵

cin >> N >> M >> K >> X;

while (M--)
{
    // 모든 경로를 입력 받음
    int A, B;

    cin >> A >> B;
    if (nodes[A] == nullptr)
        nodes[A] = new Node(A);

    if (nodes[B] == nullptr)
        nodes[B] = new Node(B);

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

Queue를 활용하는 BFS함수의 의사 코드는 다음과 같다.

1. 큐에 초기 값으로 시작 노드 삽입.
2. 큐에서 첫 번째 노드를 꺼낸다.
3. 꺼낸 노드의 모든 인접 노드 중에서 큐에 들어간 적 없는 노드를 모두 추가한다. 이때 큐에 삽입할 인접 노드의 거리는 현재 노드 거리보다 1 만큼 크다.
4. 현재 노드가 목표 거리에 있는 도시라면 현재 도시를 기록한다.
5. 현재 노드가 목표 거리를 넘어섰다면 탐색을 종료한다.
6. 큐에 노드가 존재한다면 2. 번부터 다시 반복한다.

구현

BFS함수의 코드 및 전체 소스코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
#define endl '\n'
using namespace std;

struct Node {
    Node(int num)
        :mNum(num)
        ,mDistance(-1) // 방문하지 않은 노드의 거리는 -1로 초기화.
    {}

    vector<Node*> mAdjacents;   // 인접한 노드의 집합
    int mNum;                   // 이 Node의 도시 번호
    int mDistance;              // 출발지에서 부터 거리
};

// BFS 함수 (시작 도시, 목표 거리, 노드들의 정보, 정답을 담을 벡터)
void BFS(int begin, int target, unordered_map<int, Node*>& nodes, vector<int>& answer)
{
    Node* cur;
    queue<Node*> q;
    // q에 초깃값으로 시작 노드를 삽입. 시작 노드의 거리를 0으로 초기화
    q.emplace(nodes[begin]);
    nodes[begin]->mDistance = 0;

    do
    {
        cur = q.front();
        q.pop();

        // q에서 꺼낸 노드의 인접 노드 중 q에 삽입된적 없는 모든 노드를 q에 삽입
        for (auto adjacent : cur->mAdjacents)
        {
            if (adjacent->mDistance == -1)
            {
                // 다음 노드의 거리 = 현재노드까지의 거리 + 1
                adjacent->mDistance = cur->mDistance + 1;
                q.emplace(adjacent);
            }
        }

        // 목표 거리와 동일한 거리는 모두 추가한다.
        if (cur->mDistance == target)
            answer.emplace_back(cur->mNum);

        // 목표 거리를 넘어섰다면 탐색을 종료한다.
        else if (cur->mDistance > target)
            break;

        // 큐가 비었다면 더이상 탐색을 진행할 수 없고, 탐색에 실패했음을 뜻한다.
    } while (!q.empty());

    // answer이 비었다면, 탐색에 실패했다는 뜻이기 때문에 answer에 -1을 삽입.
    if (answer.empty())
        answer.emplace_back(-1);
}


int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    // N: 도시의 개수 (2 ~ 300,000)
    // M: 도로의 개수 (1 ~ 1,000,000)
    // K: 거리 정보 (1 ~ 300,000)
    // X: 출발 도시의 번호 (1 ~ N)
    int N, M, K, X;

    vector<int> answer;             // 정답을 저장할 벡터
    unordered_map<int, Node*> nodes;// 도시 번호로 Node* 를 참조할 수 있는 해시맵

    cin >> N >> M >> K >> X;

    while (M--)
    {
        // 모든 경로를 입력 받음
        int A, B;

        cin >> A >> B;
        if (nodes[A] == nullptr)
            nodes[A] = new Node(A);

        if (nodes[B] == nullptr)
            nodes[B] = new Node(B);

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

    // BFS 실행
    // (시작 도시, 목표 거리, 노드들의 정보, 정답을 담을 벡터)
    BFS(X, K, nodes, answer);

    // 정답을 오름차순으로 정렬
    sort(answer.begin(), answer.end());

    for (auto node : nodes)
        delete node.second;

    // 정답을 모두 출력한다.
    for (auto a : answer)
        cout << a << endl;

    return 0;
}