문제 : https://www.acmicpc.net/problem/1199
과거에 알고리즘 공부를 하면서 오일러 회로에 대해서 공부 후 기본 문제에 대해서 구현을 하여 풀었던 문제입니다.
문제를 풀고 몇 달 뒤에 다시 보았을 때 데이터가 추가가 되면서 기존 답안이 시간 초과로 바뀌었습니다.
그 데이터 추가로 정답 비율이 바닥을 치게 되었고 이를 다시 해결하려고 구글링을 하여 힌트를 얻으려 했지만 당시에는 도저히 검색 결과가 나오질 않아서 스스로 고민 끝에 풀었던 기억이 있습니다.
이를 다시 복기 하면서 복습을 해보고자 다시 코드를 읽고 이 글을 작성하게 되었습니다.
우선 이 문제를 해결하려면 오일러 회로에 대한 이론을 잘 알고 있어야합니다.
기본적으로 둘 다 정점에 집중을 하는 것이 아닌 ‘간선’에 집중을 하는 문제입니다.
일반적으로 그래프에서 BFS,DFS 등으로 정점을 방문하고 visited 를 check 하는 것이 아닌
각 간선을 딱 한 번씩만 지나가고 모든 간선을 지날 수 있는지에 대해 확인하는 것입니다.
그게 가능한 경로가 오일러 경로이고 그 중에서 출발점과 도착점을 같은 경로를 오일러 회로라고 합니다.