입력으로 주어지는 그래프에는 루프 (양 끝점이 같은 간선)는 없다.
라고 되어있어서 자신으로 가는 간선은 고려하지 않는 것이 맞는 거 같습니다!
4
0 1 0 1
1 0 1 2
0 1 0 1
1 2 1 0
그래도 자신으로 가는 간선 제외한 반례에서도 완벽한 오일러 회로가 나오지 않아 틀린 이유는 찾았습니다!
노드를 모두 방문하고 처음 노드로 돌아왔는지만 체크하고 모든 간선을 사용했는지 체크하지 않아서 생긴 문제였습니다
(노드와 노드 사이 여러 간선이 있어도 사용하지 않고 최단으로 첫 노드로 돌아오는 경로만 출력함)
감사합니다~
tnqls5417 3년 전
처음에는 dfs로 파고드는 경로를 따라 출력하려고했지만 그러면 이미 간선이 없는 경로를 먼저 출력하게되어 오일러경로가 잘못됩니다.
예를 들어 질문검색의
7
0 1 1 1 0 0 1
1 0 1 0 0 0 0
1 1 0 1 0 0 1
1 0 1 0 1 1 0
0 0 0 1 0 0 1
0 0 0 1 0 0 1
1 0 1 0 1 1 0
123143754671(O) 이 아닌 123143715467(X)
그래서 백트래킹을 통해 가능한 노드로 먼저 가되 끝까지 그 경로로 갈 수 없으면 되돌아가서 한번에 오일러 경로를 출력하도록 했습니다.
위 예제와 문제 예제는 잘 나오는데 똑같이 WA네요ㅠ 시간초과면 시간부족으로 불가능하다고 생각하겠는데 틀리는 이유는 못찾겠습니다ㅠㅠ
알려주시면 감사하겠습니다.