[C/C++] 백준 - 18250번 : 철도 여행 (오일로 회로 / 경로)

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

18250번: 철도 여행

문제

한국에는 N개의 도시 C1, C2, ..., CN가 있고, 두 개의 도시를 양방향으로 잇는 M개의 철도 노선이 있다.

철도를 좋아하는 가희는 철도 여행을 하려고 한다. 철도 여행이란 시작 도시에서 도착 도시까지 철도 노선만을 이용해 이동하는데, 하나의 철도 노선을 두 번 이상 타지 않는 것을 의미한다. 시작 도시와 도착 도시는 같을 수도 있으며, 하나의 도시를 여러 번 방문할 수도 있다.

가희는 최소 횟수의 철도 여행으로 모든 노선을 정확히 한 번씩 타고자 한다. 가희가 철도 여행을 몇 번 해야 하는지 구해보자.

입력

입력의 첫 줄에 두 정수 N(1 ≤ N ≤ 200,000)과 M(1 ≤ M ≤ 300,000)이 주어진다.

이후 M개의 줄에 걸쳐 서로 다른 두 정수 u, v(1 ≤ u, v ≤ N)가 주어진다. 이는 Cu와 Cv를 양방향으로 잇는 철도 노선이 존재함을 의미한다.

단, 두 개의 도시를 직접 잇는 철도 노선은 많아야 하나이다.

출력

가희가 해야 하는 철도 여행의 최소 횟수를 출력한다.

---

문제 지문에 문제 분류가 나와있다. "모든 노선을 정확히 한 번씩 타고자 한다."

이는 오일로 회로/경로를 나타낸다. 

 

오일로 회로와 경로는 다르게 구해주어야한다.

회로는 시작 지점으로부터 모든 간선을 한 번씩 방문하여 마지막 도착지점이 시작지점과 동일해야한다.

경로는 시작 지점과 도착 지점은 다르며 간선은 한 번씩만 방문해야한다.

 

그렇기에 회로와 경로의 가장 큰 차이점은 정점들의 차수이다.

회로는 모든 정점들의 차수가 짝수개이다. 들어오고 나가는 차수가 동일해야한다.

경로는 시작 지점과 도착 지점의 차수는 홀수개이다. 다시 되돌아오지 않고 시작 지점과 끝지점이 다르기 때문에 두 노드만 정점의 수가 홀수개이다.

 

이 특성을 이용하여 문제를 해결할 수 있다.

모든 정점의 차수가 짝수이면 회로를 구성할 수 있으므로 철도 여행 1번으로 끝낼 수 있다.

 

하지만 그렇지 않은 경우에는 경로를 구성하여 철도 여행을 수행해야한다. 그리고 최소한의 철도 여행을 수행하기 위해서는 정점의 차수가 홀수인 노드로 시작 지점과 끝 지점을 지정하여야한다. 따라서 (정점의 수가 홀수인 노드의 수) / 2가 최소한의 철도 여행 수가 된다.

 

하지만 이렇게만 제출하면 맞았습니다를 받을 수 없다. 철도 여행이기 때문에 간선을 이용하여 다른 정점으로 이동할 수 있는 경우만 세어주어야한다. 정점에서 이어진 간선의 수가 존재하지 않는다면 철도 여행이라고 칭할 수 없다.

 

따라서, DFS로 다른 정점으로 이동 가능한 경우에만 철도 여행으로 판단하여 세어주어야한다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 987654321
#define endl '\n'

using namespace std;

int V, E;
int deg[200000 + 1];
bool oddPoint[200000 + 1];
bool visited[200000 + 1];
vector<int> adj[200000 + 1];

void input(){
    cin >> V >> E;
    for(int i=0;i<E;i++){
        int u, v;
        cin >> u >> v;

        deg[u]++; deg[v]++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void dfs(vector<int> &odd, int node){
    if(visited[node]) return;

    visited[node] = true;
    if(deg[node] % 2) odd.push_back(node);
    for(auto &next :adj[node]){
        dfs(odd, next);
    }
}

int solution(){
    int answer = 0;
    for(int i=1;i<=V;i++){
        if(deg[i] == 0 || visited[i]) continue;
        vector<int> oddPoint;
        dfs(oddPoint, i);
        if(oddPoint.empty()) answer += 1;
        else {
            // cout << "-> " << oddPoint.size() << endl;
            answer += oddPoint.size() / 2;
        }
    }
    return answer;
}

int main(){
    fastio;
    input();
    cout << solution() << endl;

    return 0;
}