백준 1199번 오일러 회로

문제 링크입니다: https://www.acmicpc.net/problem/1199

오일러 서킷(회로)은 그래프의 모든 간선을 정확히 한 번씩 지나면서 시작점과 끝점이 같습니다.

오일러 회로에 대한 개념은 종만북에도 잘 쓰여있고 kks227님의 블로그(https://kks227.blog.me/220800097205)에도 정말 잘 설명되어있습니다.

오일러 회로는 DFS(Depth First Search) 알고리즘을 통해 구현할 수 있습니다.

알고리즘은 아래와 같습니다.

1. 오일러 회로의 경우 모든 정점의 간선 차수가 짝수여야 합니다.

-> 두 개가 홀수여도 되는 경우는 오일러 회로가 아닌 오일러 경로 즉, 오일러 트레일입니다!

2. 오일러 회로가 될 수 있는 조건을 성립한다면 1번 정점부터 해당 정점과 연결되어 있는 정점으로 DFS 함수를 호출합니다.

-> 여기서 핵심은 DFS 함수를 호출하기 전에 해당 양방향 간선을 모두 지워주는 것입니다.

3. 2번 과정을 마치면 정점을 출력합니다.

#include <iostream>

using namespace std;

 

const int MAX = 1000 + 1;

 

int N;

int graph[MAX][MAX];

int degree[MAX]; //차수(정점으로부터 뻗어나오는 간선)

 

void DFS(int node)

{

        for(int i = 1; i <= N; i++)

                 while (graph[node][i])

                 {

                         //양방향

                         graph[node][i]--;

                         graph[i][node]--;

                         DFS(i);

                 }

        cout << node << " ";

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 1; i <= N; i++)

                 for (int j = 1; j <= N; j++)

                 {

                         cin >> graph[i][j];

 

                         degree[i] += graph[i][j];

                         degree[j] += graph[i][j];

                 }

 

        bool canEuler = true;

        for (int i = 1; i <= N; i++)

        {

                degree[i] /= 2; //양방향 간선이므로

 

                 //차수가 하나라도 홀수라면 X

                 if (degree[i] % 2)

                 {

                         canEuler = false;

                         break;

                 }

        }

 

        if (canEuler)

        {

                 DFS(1);

                 cout << "\n";

        }

        else

                 cout << -1 << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~