[백준] 1199 오일러 회로

문제
어느 점에서 출발하여 그래프 상에 있는 모든 간선을 지나되 한번 지난 간선은 다시 지나지 않고 출발점으로 돌아오는 회로를 오일러 회로라 한다. 단, 그래프는 양방향 그래프가 주어진다.

문제는 그래프가 주어졌을 때 오일러 회로 경로를 출력하는 것이다.

입력
첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 개 있을 수 있다. 인접행렬의 값은 두 정점 사이의 간선 개수를 의미하며, 0보다 크거나 같고, 10보다 작거나 같은 정수이다.

입력으로 주어지는 그래프에는 루프 (양 끝점이 같은 간선)는 없다. 또, 입력으로 주어지는 그래프는 모두 연결되어 있다.

출력
첫 줄에 방문하는 점 순서를 공백으로 구분하여 출력한다. 단, 시작점은 어느 위치에서든 상관없고 아무 경로만 하나 찍으면 된다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1
6
0 1 0 1 1 1
1 0 1 1 1 0
0 1 0 1 0 0
1 1 1 0 1 0
1 1 0 1 0 1
1 0 0 0 1 0
예제 출력 1
1 2 3 4 1 5 2 4 5 6 1

Concept

노드와 노드사이의 경로가 2개일 수 있는 오일러 회로 문제다.
오일러 회로의 조건 2가지

• 모든 노드의 degree가 짝수일 것
• 컴포넌트가 하나일 것

을 고려하면 되는 문제이다.
사실 getEuler 함수보다, main에서 고려해줘야 할 사항이 많다.
인접 행렬이 주어졌으므로, 노드의 차수를 계산할 때 중복되지 않도록 주의해야 하며, 컴포넌트의 개수를 판단하기 위해 edgeNum을 추가해주었다.

Code

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
vector<int> degree;
vector<vector<int>> adj;
vector<int> route;
int edgeNum=0;

void getEuler(int here){
    for (int there=1; there<=n; there++){
        while(adj[here][there] > 0){
            adj[here][there]--;
            adj[there][here]--;
            edgeNum--;
            getEuler(there);
        }
    }
    route.push_back(here); // 가장 먼저 push되는 것은 맨 처음 노드 본인이다(여기선 1)
}

int main(){
    cin>>n;
    adj = vector<vector<int>>(n+1, vector<int>(n+1));
    degree = vector<int>(n+1, 0);
    
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            cin>>adj[i][j];
        }
    }
    // 노드 당 차수를 계산, edge의 수도 계산
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            if (adj[i][j] > 0){
                degree[i] += adj[i][j];
                degree[j] += adj[i][j];
                edgeNum += adj[i][j];
            }
        }
    }
    
    bool oddCount=false; // 차수가 홀수인 노드가 있느냐
    for (int i=1; i<=n; i++){
        if (degree[i]%2==1){
            oddCount=true;
            break;
        }
    }
    // 차수가 홀수인 노드가 있으면 얄짤없이 탈락
    if (oddCount==true) cout<<"-1";
    else{
        getEuler(1); // 무엇으로 시작하든 상관없음.
        if (edgeNum != 0) cout<<"-1"; // 0이 아니라는 것은, 컴포넌트가 2개 이상으로 나눠져 있다는 의미이므로 탈락
        else{
            for (int i=0; i<route.size(); i++){
                cout<<route[i]<<' ';
            }
        }
    }
}

Comment

익숙해지니 할만한 문제이지 싶기도 하지만, 조건 잘 보고 main 함수에서 실수 안하는 것이 중요한 문제.