mondegreen

- 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 엄청난 시간과 메모리이다. DFS 문제를 푼 지 오래되었지만 찾아보지 않고 직접 구현해보고자 했다. 인접배열로 만들 경우 당연 n과 m의 크기 때문에 메모리를 초과할 것 같았고 어차피 배열로 순회하면 시간도 초과해버린다고 생각했다. 정점에 비해 간선이 적을 경우에는 배열보다 인접리스트를 쓰는 것이 유리하다고 기억했고 이를 활용해 구현했다. 순회하는 정점의 순서대로 값을 넣기 위해 order 배열을 생성하고 idx를 dfs 함수를 호출할 때마다 하나씩 증가시켜 값으로 넣도록 처리했다. 처음에는 dfs인자에 담아서 처리하려 했는데 같은 정점에서 뻗어나가는 간선의 경우 동일한 idx를 갖게 되어 순서가 중복되는 문제가 발생했었다. 이 코드가 최적인 것 ..