6주차(DFS와 BFS) - [C++]백준18352 특정 거리의 도시 찾기

08 Apr 2022 in Study on Algorithm

백준18352 특정 거리의 도시 찾기 링크

문제

예제 입력

---

코드

#include<iostream>
#include<climits>
#include<vector>
#include<queue>
using namespace std;

vector<int> arr[300001];
int dist[300001];

void bfs(int st) {
    queue<int> q;

    dist[st] = 0;
    q.push(st);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < arr[cur].size(); i++) {
            int next = arr[cur][i];
            if (dist[next] > dist[cur] + 1) {
                dist[next] = dist[cur] + 1;
                q.push(next);
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    int n, m, k, x;
    cin >> n >> m >> k >> x;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        arr[u].push_back(v); //인접행렬
    }
    for (int i = 1; i <= n; i++) {
        dist[i] = INT_MAX;
    }
    bfs(x); // 너비우선
    bool check = false;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == k) {
            check = true;
            cout << i << "\n";
        }
    }
    if (!check)
        cout << "-1";
}

설명

이 문제는 시작 도시에서 특정 거리만큼 떨어져 있는 도시를 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 Queue를 사용하여 구현했습니다. 도시와 단방향 도로의 정보를 입력 받고 거리를 탐색하는데 BFS로 구현했습니다. BFS는 너비우선 탐색으로 다음 상태를 모두 탐색하며 최소 거리로 갱신합니다. 그리고 특정 거리와 같은 도시들의 번호를 출력하는데 배열의 인덱스로 번호를 접근하기 때문에 따로 정렬하지 않아도 오름차순으로 결과가 출력되며 없다면 -1을 출력합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용

---

결과