[BOJ] 22868 - 산책(small)

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

BOJ - 산책(small)

문제 유형: bfs, 그래프, 그리디

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 1024MB

 

문제

코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다.

현재 있는 곳 S에서 출발하여 S와 다른 곳인 E를 찍고 다시 S로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 E에서 S로 올 때 S에서 E로 가는 도중에 방문한 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 S에서 E로 가는 가장 짧은 거리와 E에서 S로 가는 가장 짧은 거리를 원한다.

정점 S에서 정점 E로 이동할 때, 가장 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 S에서 정점 E로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 가장 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정을 해보자. 두 개의 경로중 사전순으로 먼저 오는 것은 1 3 4 2이므로 정점 1에서 정점 2로 가는 최단 경로 중 두 번째 것을 선택한다.

이와 같이 산책 경로를 정할 때, 산책 전체 경로의 거리(S에서 E로 가는 거리 + E에서 S로 가는 거리)를 구해보자.

 

입력

첫 번째 줄에는 정점의 개수 N과 두 정점 사이를 잇는 도로의 개수 M이 공백으로 구분되어 주어진다.

두 번째 줄부터 M+1 번째 줄까지 정점 A, B가 공백으로 구분되어 주어진다. 정점 A와 정점 B 사이의 거리는 항상 1이다. 이때, 정점 A와 정점 B는 양방향으로 이동해도 된다.

정점 A와 정점 B를 잇는 도로는 두개 이상 주어지지 않는다.

 M+2번째 줄에는 정점 S와 정점 E가 공백으로 구분되어 주어진다.

산책을 할 수 있는 경로가 있는 데이터만 주어진다.

 

출력

산책의 전체 경로의 길이를 출력한다.

 

풀이

인접 리스트를 만들어서 정렬하고, 그 뒤 최단거리 알고리즘을 적용하면, 사전순이 보장된다.

s -> e로 최단거리 이동을 하면서, 이전의 노드를 마킹한다. 역추적하며 경로에 쓰인 노드들을 비활성화 시키고, e -> s로 최단거리 이동을 하여 두 번의 bfs동안의 거리를 더해서 출력하면 된다.

 

코드

C++

#include <bits/stdc++.h>
using namespace std;

int ans = 0;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);
    vector<bool> visited(n + 1, false);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end());
    }

    int s, e;
    cin >> s >> e;

    queue<int> q;
    vector<int> past(n + 1, INT_MAX);
    vector<int> dist(n + 1, INT_MAX);
    dist[s] = 0;
    q.emplace(s);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        if (curr == e) break;

        for (const auto &next : adj[curr]) {
            if (dist[next] > dist[curr] + 1) {
                q.emplace(next);
                dist[next] = dist[curr] + 1;
                past[next] = curr;
            }
        }
    }

    ans += dist[e];
    int node = e;
    while (node != INT_MAX) {
        visited[node] = true;
        node = past[node];
    }

    past = vector<int>(n + 1, INT_MAX);
    dist = vector<int>(n + 1, INT_MAX);
    visited[s] = false;
    dist[e] = 0;
    q = queue<int>();
    q.emplace(e);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        if (curr == s) break;

        for (const auto &next : adj[curr]) {
            if (visited[next]) continue;
            if (dist[next] > dist[curr] + 1) {
                q.emplace(next);
                dist[next] = dist[curr] + 1;
                past[next] = curr;
            }
        }
    }
    ans += dist[s];

    cout << ans << "\n";

    return 0;
}