Eulerian Path / Eulerian Circuit (오일러 경로 / 오일러 회로)
코드
정리
- 그래프에 존재하는 모든 간선을 정확히 한번씩만 방문하는 연속된 경로 (한붓 그리기)
- 시작점과 도착점이 같으면 오일러 회로(한붓 그리기)
- 오일러 경로의 존재 여부를 판단하는 방법
- 무향 그래프의 경우 차수가 홀수인 정점이 2개일 때 오일러 경로
- 무향 그래프의 경우 차수가 홀수인 정점이 0개일 때 오일러 회로
관련 문제
- 1199 : 오일러 회로
- 1616 : 드럼통 굴리기 ★
- 1591 : 수열 복원 ★