2주차 개념#12 트리 순회
이 부분에서 postOrder 함수작성에서 제가 작성했던 코드도 괜찮으 postOrder 형태인지 알고싶습니다!
void postOrder(int here) {
if (!visited[here]) {
for (int v : adj[here]) {
postOrder(v);
}
visited[here] = 1;
cout << here << " ";
}
}답변 2
0
안녕하세요 ㅎㅎ
출력순서는 postorder인데 visited 적용 순서를 이렇게 바꾸는게 좋습니다.
void postOrder(int here) {
visited[here] = 1;1.코드는 개발자의 올바른 의미를 담아야 합니다. 이 지점을 먼저 방문했다는 의미를 담아야 합니다.
사이클을 방지해야 합니다.
예를 들어 현재 코드는 visited가 늦게 찍히기 때문에, 사이클이 있으면:
A → B → A → B … 형태로 계속 재귀가 돌 수 있습니다.
50% postorder 코드라고 보시면 됩니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. kjmhs501님.
질문해주신 postOrder 함수는 트리 순회를 구현하는 과정에서 흔히 사용하는 방식 중 하나인 후위 순회(PostOrder Traversal)를 구현하려고 하신 듯합니다. 후위 순회에서는 왼쪽 자식, 오른쪽 자식을 방문한 후 자신을 방문합니다.
작성하신 코드에서 주의할 점은, DFS(깊이 우선 탐색)에서는 자식 노드를 정확히 탐색한 뒤에 루트 노드를 방문하도록 구성해야 하는데, 현재 코드에서는 visited 변수를 사용하여 이미 방문한 노드를 또 방문하지 않도록 하고 있습니다. 만약 트리 구조에서 중복 방문을 방지하기 위한 것이라면 방문 체크는 괜찮은데, 일반적인 트리 순회에서는 이 변수를 사용하지 않는 경우가 많습니다. 왜냐하면 트리는 사이클이 없는 비순환 그래프이기 때문입니다.
하지만 만약 이 코드가 그래프 구조에서의 후위 순회를 구현하려는 목적이라면, visited가 필요할 수 있습니다. 무방향 그래프에서 후위 순회를 구현할 때는 자식 노드 방문 후 현재 노드를 방문하는 순서를 지킴으로, 트리 순회 로직에 맞게 잘 작성된 것입니다.
추가적으로, 유사한 질문의 해결책을 찾고 싶다면 아래 링크를 참조해 주세요:
- “2주차 개념 #9 깊이우선탐색 예제 질문 입니다.” - 깊이 우선 탐색과 관련된 예제에 대한 설명이 있으니 참고가 되실 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
코딩살구클럽 승인
0
11
1
DP 경우의 수 설명이 이해가 되지 않습니다.
0
21
2
3-F 채점 관련 질문
0
18
1
BFS, DFS 활용이 되는 상황에서의 방향성
0
25
2
코딩살구클럽 승인
0
37
2
코딩살구클럽승인
0
29
3
코딩살구클럽 승인
0
47
2
3-D 관련 질문
0
34
2
코살구 회원가입 문의
0
41
2
코살구 로그인 문제
0
64
2
3-A 문제 풀이 관련 질문
0
52
3
2-O 질문 있습니다
0
38
2
2-T 문제에 관한 질문
0
40
2
코딩 살구 클럽 접속 및 사용방법 문의
0
61
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
64
2
코딩살구클럽 로그인문제
0
76
3
코딩 살구 클럽 로그인 문제
0
82
2
2-J 채점관련 질문
0
65
3
코딩 살구 클럽 Python 지원 가능 여부
0
77
1
살구클럽 아이디 없음 문제
0
76
1
1-O 코딩살구클럽 채점관련 질문
0
60
2
히든 테스트 케이스가 사라졌습니다
0
57
1
채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요
1
74
2
살구 클럽 채점 관련 문의(테스트 케이스)
0
66
2