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