[백준/자바] 16168 퍼레이드

16168 퍼레이드 사진 클릭시 문제로 이동

---

문제

종우는 18학번을 대표하여 중앙대학교 개교 100주년 기념 퍼레이드의 경로 선정 위원으로 선정되었다. 퍼

레이드의 경로는 일정한 지점들과 두 지점을 연결하는 연결 구간으로 이루어져 있다.

종우는 모든 지점을 지나면서 모든 연결 구간들을 지나고 싶어 한다.

하지만 같은 연결 구간을 두 번 이상 지날 경우 그 구간의 주민들이 민원을 제기하게 된다.

단, 같은 지점은 두 번 이상 지나도 된다.

민원을 받지 않으면서 모든 구간을 지나도록 퍼레이드를 만들고 싶은 종우를 위한 프로그램을 작성해보도록 하자.

입력

첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000)

이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다.

(1 ≤ Va, Vb ≤ V, Va ≠ Vb)

서로 다른 두 연결 구간 (Va1, Vb1), (Va2, Vb2)에서 Va1 = Va2 & Vb1 = Vb2 인 경우는 존재하지 않으며,

임의의 지점에 적어도 하나의 연결 구간이 연결되어 있음이 보장된다.

출력

종우가 원하는 노선을 만들 수 있다면 YES, 아니면 NO를 출력한다.

예제 입력 1

4 5
1 2
1 3
1 4
2 3
2 4

예제 출력 1

YES

예제 입력 2

5 8
1 2
1 3
1 4
1 5
2 3
2 4
3 5
4 5

예제 출력 2

NO

---

설명

오일러 경로 문제다.

오일러 경로는 출발지와 목적지가 다른 한붓 그리기로 생각하면 쉽다.

이는 출발지와 목적지 간점은 홀수개의 간선을 나머지는 짝수개의 간선을 가진 것을 이용해 문제를 해결할 수 있다.

다만 그렇게 문제를 해결하기 위해서는 그래프가 하나의 덩어리인지 판단하는 요소도 필요하다.

 

ArrayList <Integer>[] al을 사용해 연결된 간선을 표시한다.

int circuit [][]으로 이전에 간선을 사용했는지 여부를 표시한다.

이전에 사용한 간선이라면 다시 사용하지 않고 사용하지 않은 간선이라면 사용해 다시 재귀를 돌게 된다.

dfs를 재귀로 따라가다 모든 간선의 개수만큼 count 됐다면 이는 모든 간점을 지나면서 모든 간선을 사용한 것으로 판단해 "YES"를 표시한다.

코드