백준 1199번 - 오일러 회로

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

1199번: 오일러 회로

# Approach)

오일러 회로를 구성하는 알고리즘, Hierholzer's Algorithm에 대해 배우는 문제이다.

 

 

# Logic)

Hierholzer's Algorithm을 그대로 적용하자. TLE를 피하기  위하여 본 포스트에서는 인접행렬대신 인접리스트를 이용하여 구현할것이다.

 

1.  간선의 정보를 저장해준다.

각각의 간선의 정보를 간선의 리스트 edges에 넣어준후, 각 정점(v)에서 간선의 정보를 취득 할 수 있도록 해당 간선의 인덱스를 추가해준다. 

 cin >> edge;
 edges.push_back(edge);
 adj[edge.a].push_back(edges.size()-1);
 adj[edge.b].push_back(edges.size()-1);

2. 오일러 회로인지 판별한다.

오일러 회로이기 위한 필요충분조건은 "회상의 모든 정점의 차수(degree)가 짝수"이다.

따라서 정점을 돌며 차수의 홀짝성만 검사하면 되고 의사코드는 다음과 같다.

bool is_euler_circuit {
  for(int v in graph) {
  	int deg = 0;
    for(int edge_idx: adj[v]) deg += edges[edge_idx].cnt;
    if(deg & 1) return 0;
    //Every vertext can be the start point
    //So you can fix to any point in the graph if it's euler circuit
    if(start == -1) start = i;
  }
}

3. 오일러 회로가 맞다면 회로를 재구성해주어야하고 dfs를 통해 이를 달성해줄것이다.

dfs의 논리는 어렵지 않다. 한 정점에서 시작하여 해당 정점에서 도달 할 수 있는 모든 정점을 방문해주며 재귀적인 호출을 반복해주는 것이다.

 한번의 dfs호출을 살펴보자. dfs(idx)가 호출되었을때 함수의 동작은 해당 인덱스를 가장 마지막에 출력(vector에 저장하는 것이라면 단순히 push_back해주면 될 것이다)하며 dfs(idx) 내부에서 재귀호출되는 dfs들은 뭔가의 경로를 거쳐

해당 인덱스 idx로 도달하는 경로들을 포함하게 될 것이라는 것을 알 수 있다.

idx로 들어오는 경로들이 dfs호출로 모두 저장되게 되는 셈이며 모든 정점의 차수가 짝수인것은 이미 확인했으므로

$path(1) \to v_{idx} \to path(2) \to v_{idx} \to path(3) \ldots \to path(2k) \to v_{idx}$

의 경로로 $v_{idx}$에서 출발하여 $v_{idx}$로 돌아오는 경로가 생성됨을 알 수 있다. 이러한 묶음이 재귀적으로

묶이게 되고 최종적으로는 모든 dfs함수가 호출 및 종료 된 시점에선 우리가 단계 1에서 임의로 지정해준 $v_{start}$에서 출발하여 다시 $v_{start}$로 돌아오는 회로가 형성되는 것이다.

---

문제에서 정점 $u, v$를 잇는 간선이 2개이상일수도 있다는 문제는

edge 구조체에 cnt속성으로 간선의 개수를 저장함으로써 처리해줄 수 있게 된다.

 

#Code(c++)

#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define pf first
#define ps second
#define pii pair<int,int> 
#define ll long long
#define lll __int128
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int INF = 987654321;
const ll INFLL = 1e13;
// const int mod = (int)1e9+7;
const int mod = 32768;
const int N = 802;
const int st = 50;
// const int N = 1000000;
int n, m, t, k, start = -1, ans = 15;
// int adj[1001][1001];
vector<vector<int>> adj;

struct Edge{
  int u, v;
  int cnt;
  Edge(int _u, int _v, int _c): u(_u), v(_v), cnt(_c) {};
};

vector<Edge> edges;

bool chk() {
  for0(i, n) {
    int deg = 0;
    for(auto eidx: adj[i]) deg += edges[eidx].cnt;
    if(deg & 1) return 0;
    if(start == -1) start = i;
  }
  return 1;
}

void dfs(int cur) {
  while(adj[cur].size()) {
    int eidx = adj[cur].back();
    if(edges[eidx].cnt) {
      while(edges[eidx].cnt > 0) {
        edges[eidx].cnt--;
        dfs(edges[eidx].u + edges[eidx].v - cur);
      }
    }
    else adj[cur].pop_back();
  }
  cout << cur + 1 << dkdk;
}

void solve() {
  for0(i, n) {
    for0(j, n) {
      int in; cin >> in;
      if(i <= j && in) {
        edges.push_back({i, j, in});
        int eidx = edges.size() - 1;
        adj[i].push_back(eidx);
        adj[j].push_back(eidx);
      }
    }
  }
  if(!chk()) {
    cout << -1;
    return;
  }
  dfs(start);
}

int main() {
  FASTIO; 
  // freopen("input.txt", "r", stdin);
  cin >> n;
  adj.resize(n);
  solve();
}