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
51
2
코딩살구클럽 가입문의
0
58
2
3-K private case 질문
0
59
2
안녕하세요. 코딩살구클럽 문의드립니다!
0
72
2
7:41 듣다가 질문합니다
0
67
2
코드 리뷰 요청드립니다!
0
72
2
코딩살구클럽 계정 문의
0
74
2
SK하이닉스 대비 강의수강
0
206
3
코딩살구클럽 등록부탁드립니다.
0
71
2
7-F 재귀로 풀시 런타임애러
0
69
1
1-N 문제 질문입니다. (+ 채점오류)
0
79
2
코딩살구클럽 가입 확인 부탁드립니다.
0
83
2
직장인 코테 합격 공부방법 문의
0
114
2
코딩살구클럽 가입 방법
0
91
2
6-H 체점 관련 질문
0
72
1
채점서버 연결 관련 질문입니다
0
99
2
삼성 s직군
0
87
1
삼성 코테 없어짐
0
207
1
코딩살구클럽 가입부탁드립니다
0
87
2
코딩살구클럽 가입 요청 확인부탁드립니다
0
67
2
5-S 테스트 케이스 질문
0
73
2
코살 문제풀이 환경
0
85
2
2 - T 오큰수 문제가 있는 것 같습니다.
0
76
1
추천 추가문제들
0
70
2