[백준 BOJ] 18352번 특정 거리의 도시 찾기 (C++/cpp)

문제 설명

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

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

 

접근 방법 - 그래프 탐색의 심화문제 (BFS)

백준의 18352번 문제는 그래프 탐색에 대하여 다소 심화된 내용을 다루고 있는 문제이다.

해당 문제는, 도시 간의 도로 연결 상태, 시작점, 거리 정보가 주어질 때 주어진 거리 정보가 시작점에서부터의 최단 거리인 도시의 번호를 찾아 출력해야 하는 문제이다.

문제의 태그에도 나와있다시피, 이 문제는 BFS를 이용하여 해결해야 한다.

필자의 경우엔, 단방향으로 주어진 도로의 정보를 효율적으로 접근하기 위해 벡터 배열을 응용해 보았다.

그리고 BFS이기 때문에 당연히 큐와 방문 여부를 저장할 배열도 함께 이용하여 이 문제를 해결하였다.

이때, visit은 방문 여부를 나타내기도 하지만 최종적으론 시작점으로부터의 최단 거리를 저장하게끔 하였다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 단방향 도로 정보를 저장할 벡터 배열(v)과 각 도시의 방문 여부를 저장할 배열(visit)을 전역 변수로 미리 선언해 둔다.

 

2) 도시의 개수(city), 도로의 개수(road), 거리 정보(min), 시작점(start)을 순차적으로 입력받는다.

그리고 road의 크기만큼 단방향 도로 정보를 입력받고, 그 즉시 v에 저장한다.

v[a].push_back(b);	// a->b 방향의 단방향 도로 정보 추가

 

3) 현재 위치의 도로 번호와 현재까지의 거리 정보를 함께 저장할 큐(q)를 선언한다.

그리고 시작점인 도시 번호와 현재까지의 거리 정보(0)를 즉시 q에 저장하도록 한다.

 

4) q가 완전히 빌 때까지, 아래의 연산을 취한다.

- q의 front 값을 추출하여 각 변수에 저장한 뒤, 즉시 pop 연산을 취한다. (now: 현재 도시 번호, k: 현재까지의 거리 정보)

- 현재 위치의 도시 번호가 시작점과 같지 않고 아직 방문하지 않은 도시라면, now를 인덱스로 갖는 visit의 배열값을 k로 변경한다. (최단 거리 저장)

- 다음으로 갈 수 있는 도시를 탐색한다.

현재 위치 now와 연결된 도시 중 방문하지 않은 도시가 있다면, 이 도시의 번호를 q에 push하도록 한다.

이때, 거리 정보는 현재 위치에서 다음 위치로 가면서 1 증가하기 때문에 k+1로 저장한다.

 

5) 주어진 최단 거리에 있는 도시가 있는지에 대한 여부를 저장할 변수 cnt를 0으로 초기화하여 선언한다.

 

6) 모든 도시 번호에 대한 visit의 값들을 탐색한다.

만일 min과 동일한 값을 가진 배열값을 찾았다면, 해당 도시 번호를 출력한다. cnt에도 1을 추가한다.

 

7) 만일 어떤 도시 번호도 출력되지 않고 cnt가 0이라면, -1을 출력한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#define endl '\n'
using namespace std;

//백준 18352번 코드
vector<int> v[300001];
int visit[300001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int city, road, min, start;
    cin >> city >> road >> min >> start;
    for (int i = 0; i < road; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
    }

    queue<pair<int, int>> q;
    q.push(make_pair(start, 0));
    while (!q.empty()) {
        int now = q.front().first;
        int k = q.front().second;
        q.pop();

        if (now != start && visit[now] == 0) {
            visit[now] = k;
        }

        for (int i = 0; i < v[now].size(); i++) {
            if (visit[v[now][i]] == 0) {
                q.push(make_pair(v[now][i], k + 1));
            }
        }
    }

    int cnt = 0;
    for (int i = 1; i <= city; i++) {
        if (visit[i] == min) {
            cout << i << endl;
            cnt++;
        }
    }
    if (cnt == 0) {
        cout << -1 << endl;
    }
}

 

제출 결과

(2023.01.20 백준 18352번 문제 제출 결과)