2주차 개념#12 트리 순회

Question

이 부분에서 postOrder 함수작성에서 제가 작성했던 코드도 괜찮으 postOrder 형태인지 알고싶습니다! void postOrder(int here) { if (!visited[here]) { for (int v : adj[here]) { postOrder(v); } visited[here] = 1; cout << here << " "; } }

큰돌 · Answer

안녕하세요 ㅎㅎ 출력순서는 postorder인데 visited 적용 순서를 이렇게 바꾸는게 좋습니다. void postOrder(int here) { visited[here] = 1; 1.코드는 개발자의 올바른 의미를 담아야 합니다. 이 지점을 먼저 방문했다는 의미를 담아야 합니다. 사이클을 방지해야 합니다. 예를 들어 현재 코드는 visited가 늦게 찍히기 때문에, 사이클이 있으면: A → B → A → B … 형태로 계속 재귀가 돌 수 있습니다. 50% postorder 코드라고 보시면 됩니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. kjmhs501님. 질문해주신 postOrder 함수는 트리 순회를 구현하는 과정에서 흔히 사용하는 방식 중 하나인 후위 순회(PostOrder Traversal)를 구현하려고 하신 듯합니다. 후위 순회에서는 왼쪽 자식, 오른쪽 자식을 방문한 후 자신을 방문합니다. 작성하신 코드에서 주의할 점은, DFS(깊이 우선 탐색)에서는 자식 노드를 정확히 탐색한 뒤에 루트 노드를 방문하도록 구성해야 하는데, 현재 코드에서는 visited 변수를 사용하여 이미 방문한 노드를 또 방문하지 않도록 하고 있습니다. 만약 트리 구조에서 중복 방문을 방지하기 위한 것이라면 방문 체크는 괜찮은데, 일반적인 트리 순회에서는 이 변수를 사용하지 않는 경우가 많습니다. 왜냐하면 트리는 사이클이 없는 비순환 그래프이기 때문입니다. 하지만 만약 이 코드가 그래프 구조에서의 후위 순회를 구현하려는 목적이라면, visited 가 필요할 수 있습니다. 무방향 그래프에서 후위 순회를 구현할 때는 자식 노드 방문 후 현재 노드를 방문하는 순서를 지킴으로, 트리 순회 로직에 맞게 잘 작성된 것입니다. 추가적으로, 유사한 질문의 해결책을 찾고 싶다면 아래 링크를 참조해 주세요: &ldquo;2주차 개념 #9 깊이우선탐색 예제 질문 입니다.&rdquo; - 깊이 우선 탐색과 관련된 예제에 대한 설명이 있으니 참고가 되실 수 있습니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.