순회 순서 질문

Question

선배님 DFS 순회 순서에 대해 질문이있어서 글 남깁니다. void DFS(int now) { //전위 cout << now << endl; visited[here] = true; for(int next = now ; next < length ; ++next) { if(visited[next]) continue; } //후위 cout << now << endl; } 질문 1. 주석에 써넣은대로 전위 후위 순회가 맞나요? 질문 2. 그래프에는 중위 순회가 존재하지 않는건가요? 질문 3. visited[here]의 위치는 항상 포문 위쪽에 고정되어야 하는건가요? 후위순회라면 방문 기록도 밑에 있어야할 것 같은데 포문 아래쪽에 작성하게 되면 동작이 원하는대로 되지 않아서요.. 이해를 잘못한건지ㅠㅠ 궁금합니다

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴이에요. 질문에 답변 드리겠습니다. 질문 1에 대한 답변입니다. 주석에 써넣은 대로 전위 후위 순회가 맞습니다. 해당 코드에서는 노드를 방문한 후 자식 노드를 탐색하기 전에 전위 순회를 하고, 모든 자식 노드를 탐색한 뒤 해당 노드를 다시 출력하는 후위 순회를 하고 있습니다. 질문 2에 대한 답변입니다. 그래프에서는 일반적으로 중위 순회를 사용하지 않습니다. 중위 순회는 주로 이진 트리에서 사용되는 방법이므로 그래프에서는 잘 쓰이지 않습니다. 중위 순회는 좌우 순서를 중요시하기 때문에 그래프의 환경에 적합하지 않을 수 있습니다. 질문 3에 대한 답변입니다. visited[here]의 위치는 항상 포문 위에 고정되어야 하는 것은 아닙니다. 후위 순회라면 방문 기록도 포문 아래에 작성해도 되는데, 포문 위에 작성했을 때 동작이 원하는 대로 되지 않는다는 말씀이시죠? 이 부분은 코드의 구현 방식에 따라 달라질 수 있습니다. 일반적으로는 전위 순회에서 방문 기록은 포문 위에 작성하고, 후위 순회에서는 포문 아래에 작성하는 것이 일반적입니다. 그렇지만 구체적인 구현 방식이나 사용되는 변수에 따라 방문 기록의 위치를 조정해야 할 수도 있습니다. 코드의 동작 방식을 다시 확인해보시고, 원하는 결과가 나오지 않을 때는 코드를 재검토해보시기를 권장드립니다. 더 궁금한 점이 있으시면 언제든지 물어보세요. 좋은 하루 되세요!