[DFS] 백준 1199번 오일러 회로 C++ 풀이

문제 링크

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

오일러 경로 및 오일러 회로

• 공통점
  • 무향이나 유향 그래프가 있을 때,
  • 그래프에 존재하는 모든 간선을 정확히 1번 씩만 방문하는 연속된 경로
• 차이점
  • 시작점과 도착점이 다르면 오일러 경로
  • 시작점과 도착점이 같으면 오일러 회로

오일러 경로 및 회로의 존재 여부 판단

• 무향(or 양방향) 그래프의 경우

  • 차수가 홀수인 정점이 2개일 때, 오일러 경로 존재
    • 즉, 시작점과 도착점의 차수만 홀수일 때
  • 차수가 홀수인 정점이 0개일 때, 오일러 회로 존재
    • 즉, 모든 정점의 차수가 짝수일 때
      • 무향 그래프이기 때문에, 시작점과 끝점을 제외하고서는, 들어오는 간선이 있다면 반드시 나가는 간선이 하나 더 있어야한다.
      • 따라서, 차수는 항상 2의 배수꼴을 가진다.

• 유향 그래프의 경우

  • 오일러 경로
    • 시작점과 도착점을 제외한 나머지 정점의 indegree 와 outdegree 가 일치해야한다.
      • indegree 가 1 적은 정점 하나가 시작점, outdegree가 1 적은 정점 하나가 도착점으로 정해진다.
      • 물론, 1 씩 차이가 나지 않아도 안된다.
  • 오일러 회로
    • 모든 정점에 대해 indegree 와 outdegree 가 일치해야한다.

• 무향 / 유향 관계없이

  • 서로 다른 컴포넌트에 각각 간선이 존재해도 오일러 경로는 존재할 수 없다.
    • 두 컴포넌트 자체가 떨어져 있어서 절대 경로를 이을 수 없기 때문이다.
  • 그러나 컴포넌트에 간선이 없고 정점만 떨어져 있다면, 오일러 경로는 존재한다.

Hierholzer's Algorithm

• 오일러 회로를 구할 때 사용되는 알고리즘이다.
• 개념
  • ① 아무 정점 v 를 뽑고, v 에서 출발해 v 로 돌아오는 경로를 탐색한다.
  • ② 이때, 아직 방문되지 못한 간선이 있는 정점 u 가 존재하면,
  • ② u 에서 시작해서 아직 쓰이지 않은 간선들만 사용해, u 로 돌아오는 경로를 하나 더 찾아, 원래의 경로에 끼워넣는다.

DFS 를 사용한 해결

• A 에서 출발해 A 로 돌아오는 경로를 [A, B, C, D] 로 탐색했다고 가정하자.
• 이때, C 에서 또다른 경로 [C, E, F, C] 를 찾아, 원래의 경로에서 C가 있던 자리에 대체해서 끼워 넣으면, [A, B, C, E, F, C, D, A] 가 되어 오일러 회로가 완성된다.
• 이는, DFS 를 통해 해결할 수 있다.
• 정점에서 정점으로 이동할 때, 해당 정점들은 1개의 간선을 사용했기 때문에, 양쪽 정점의 차수를 1씩 줄여 나간다.
• 방문한 정점의 차수가 0 이라면, 정점 번호를 출력하고, 함수를 종료한다.
• 이를 반복하면 정답이 된다.
• Example1
  • 예를 들어, A -> B -> C 순으로 방문했다고 가정하자.
  • 만약, 여기서 D 를 먼저 택해도, D -> A 로 가서 A의 이웃이 더 없으므로 방문이 끝나, C 로 돌아오면서 "A D" 를 출력하게 된다.
  • 그 다음, 남은 정점 E를 선택해서 C -> E -> F -> C 로 가면 C 도 더 이상 이웃이 없어서 그대로 돌아가며 "C F E C"를 출력하고,
  • C 에서도 시작점인 A 로 돌아가면서 "B A" 를 출력하면
  • "A D C F E C B A" 가 되고 이건 오일러 회로이다.
• Example2
  • 만약, A -> B -> C 를 방문하고, D 가 아니라 E 를 먼저 방문했다고 해도,
  • C -> E -> F -> C 를 방문한 후, C 에서 이제 유일하게 남은 D 를 방문하는 순서를 거치게 되고
  • 결과를 이으면 "A D C F E C B A" 가 되어, 또 오일러 회로이다.

코드

#include <string>
#include <iostream>
#include <algorithm>
#define MAX 1000
using namespace std;

// 정점의 수
int n;

// 인접행렬
int adj_matrix[MAX][MAX];

// 정점 차수
int degree[MAX];

// 오일러 회로 탐색 함수
void eulerain_circuit(int current_node){

    // 현재 정점의 차수 계산
    for (int i=0; i<n; ++i){

        // 간선이 존재한다면
        if (adj_matrix[current_node][i] != 0){

            // 간선을 가지는 정점의 차수를 -1 씩 감소한 뒤, 연결된 정점을 탐색
            adj_matrix[current_node][i] -= 1;
            adj_matrix[i][current_node] -= 1;
            eulerain_circuit(i);            
        }
    }
    // 현재 정점 출력
    cout << to_string(current_node+1) << " ";
}

int main(void){

    // 정점 개수 입력
    cin >> n;

    // 입력에 따른, 인접행렬 초기화
    for(int i=0; i<n; ++i){
        for (int j=0; j<n; ++j){

            // 인접행렬 요소 입력
            cin >> adj_matrix[i][j];

            // 인접행렬의 한 행을 모두 탐색하며, 한 정점의 모든 간선 개수 덧셈
            degree[i] += adj_matrix[i][j];
        }
    }

    // 인접행렬 한 정점의 차수가 홀수라면 오일러 회로 불가능
    for (int i=0; i<n; ++i){
        if (degree[i] % 2 == 1){
            cout << -1 << endl;
            return 0;
        }
    }

    // 재귀 함수 호출
    eulerain_circuit(0);

    return 0;

}

참고

• https://blog.naver.com/kks227/220800097205