첫 번 째 예제에서 오답을 출력합니다

DFS에서 현위치 "s"에서 바로 갈 수있는 정점 e를 스택에 넣을 때, 동시에 visited[e]를 True로 설정을 하는데, 이는 e정점을 스택에서 꺼내서 탐색하기 전에 이미 방문 했다는 표시를 하게 되기 때문에 DFS의 출력 결과가 틀리게 나옵니다.

반례를 예로 들면

1에서 시작하면 [2, 3, 4]를 보게 되고 이 visited[2], visited[3], visited[4]를 True로 찍고, 4, 3, 2 순으로 스택에 들어갑니다. 그 다음, 스택에서 2를 꺼냈을 때, 2와 인접해 있는 정점은 1과 4가 있습니다. 1은 탐색을 이미 했고 4는 아직 하지 않은 상태이기 때문에 1 -> 2 -> 4가 되어야 하지만, 위 코드에서는 이미 visited[4]를 True로 설정했기 때문에 한 번 방문을 했다고 판단하고, 스택에 아무것도 추가하지 않게 되고, 3을 꺼냄으로써 1 -> 2 -> 3 이라는 오답을 출력합니다.

BFS야 어차피 다음 탐색 순서가 해당 정점의 인접해 있는 정점들이기 때문에 큐에 추가함과 동시에 visited를 True로 설정해도 문제가 없지만, DFS는 이렇게 하면 탐색을 아직 하지 않았음에도 이미 했다고 판단을 하게 됩니다.

감사합니다. 코드 수정하면서 테스트케이스 검사하다가 틀린걸 못봤네요