[백준 1199] 오일러 회로(인접 리스트) (C++)

[백준 1199] 오일러 회로 C++

 

예전에 풀었던 오일러 회로 문제가 인접행렬로 풀 수 없게 데이터가 추가되면서 많은 사람들이 시간초과의 늪에 빠졌었다.

나도 마찬가지로 시간초과로 틀리게 되었고 4달이 지나서야 인접 리스트 방식의 오일러 회로를 공부하고 다시 풀게 되었다.

---

INPUT

우선 input 부분에 많은 변화가 있었다.

 

i에서 j로 가는 간선을 인접 행렬로 저장하지 않고 간선 그 자체로 저장했다.

대신에 j에서 i로 가는 간선은, 입력에서 i에서 j로 가는 값과 똑같기 때문에 따로 처리하지 않았다.

쉽게 말해서 정방 행렬에서 위쪽 삼각형 부분만 저장했다.(아래쪽 삼각형과 대칭되기 때문에.)

 

i에서 j로 가는 간선의 번호(edgecount)를 저장하고 해당 번호를 가진 간선이 몇 개가 있는지 edgenum[1000001] 배열에 저장했다.

배열이 100만의 크기를 갖는 이유는 정점(N)이 최대 1000개 이므로 최대 N*(N-1)/2개의 간선을 가질 수 있어서 편하게 N^2 크기의 배열을 잡았다. 

 

마지막으로 i와 j를 시작점으로 하는 adj[i], adj[j]에 간선의 번호(edgecount)를 각각 추가해 줌으로서 해당 정점과 연결된 간선을 표시했다.

---

findEuler

처음에 while(adj[now].size())대신에 for(int i = 0; i < adj[now].size(); i++) 를 사용해서, 현재 now 정점에 연결된 간선의 번호를 찾으려고 했다. 하지만 for문으로 벡터의 원소에 접근하는 방식은 재귀적으로 들어가면서 adj[now]의 간선을 방문하고 pop 처리를 하게 되는데, 이때 되돌아오면서 아직 pop 되기 전의 size()로 for문을 돌고 있기 때문에 segmentation fault가 반드시 발생할 수 밖에 없다.

그래서 while문을 사용해서 안정적으로 pop을 할 수 있도록 했다.

 

현재 정점에 연결된 간선의 수가 하나 이상이라면 해당 간선의 수를 하나 감소시키고 재귀적으로 그래프를 탐색한다.

만약 간선이 없다면 now정점에 연결된 현재 간선은 모두 사용되었다는 뜻이므로 pop을 수행한다.

 

오일러서킷 벡터에 입력된 순서는 도착지점부터 역순으로 입력되어있으므로 reverse함수를 사용해 다시 역순으로 출력해준다.

(오일러 서킷 특성상 역순으로 출력 할 필요는 없어보인다.)

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
 
using namespace std;
 
int N;
vector<int> Eucircuit;
 
vector<int> adj[1001];
vector<pii > edge;
int edgenum[1000001];
int edgecount;
 
void findEuler(int now){
    while(adj[now].size()){
        int e = adj[now].back();
        int u = edge[e].first;
        int v = edge[e].second;
        if(u > v) swap(u, v);
        if(edgenum[e]){
            edgenum[e]--;
            if(u == now) findEuler(v);
            else findEuler(u);
        }
        else adj[now].pop_back();
    }
    Eucircuit.push_back(now);
}
 
bool input(){
    cin >> N;
    int a;
    for(int i = 1; i <= N; i++){
        int degree = 0;
        for(int j = 1; j <= N; j++){
            cin >> a;
            degree += a;
            if(i >= j || !a) continue;
            edge.push_back({i, j});
            edgenum[edgecount] += a;
            
            adj[i].push_back(edgecount);
            adj[j].push_back(edgecount++);
        }
        if(degree % 2) return false;
    }
    return true;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if(!input()){
        cout << -1;
        return 0;
    }
    
    findEuler(1);
    reverse(Eucircuit.begin(), Eucircuit.end());
    
    for(auto &w : Eucircuit){
        cout << w << " ";
    }
    
    return 0;
}