[백준/자바] 1199 오일러 회로

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

---

설명

오일러 회로를 구하는 문제다.

오일러 회로는 처음과 끝이 같은 한붓 그리기를 생각하면 쉽다.

오일러 회로가 되기 위해서는 당연히 두 개 이상의 컴포넌트로 나뉘어 있으면 안 된다.

한 개의 컴포넌트로 구성되있을때, 모든 정점의 차수가 짝수가 되면 오일러 회로가 된다.

코드