인프런 커뮤니티 질문&답변

안녕하세요 용근님 ㅎㅎ

보통 트리 구조에서는 부모 노드가 먼저 나오고, 번호도 부모부터 매기는 경우를 많이 봤습니다. 그리고 예제 입력도 그런 형태로 주어져서, 부모 노드가 자식 노드보다 먼저 입력된다는 전제로 코드를 작성했습니다.

이 부분이 잘못된 부분이 맞을까요?

-> 네 맞습니다. 부모가 뒤에서 처음 등장하고 자식이 앞쪽에 있는 경우, 손자·증손자처럼 깊이가 2 이상인 경우, 자손을 일부 놓치게 됩니다.

또, 이런 상황이 발생하지 않도록 하려면 어떤 식으로 코드를 짜는 게 좋을지도 궁금합니다.

-> 문제를 푸실 때 문제설명을 기반으로 풀어야 합니다. (문제에서 부모 노드가 자식 노드보다 먼저 입력된다는 전제가 있지 않은데 그걸기반으로 생각x) + 그렇게 해서 로직을 구축했다면 -> 반례들을 생각하면서 풀면 됩니다. (반례는 문제 범위의 최소, 최대를 중점을 생각하는게 좋습니다. 예를 들어 최소가 0이고 최대가 10만이라면 입력값에 0이나 10만을 넣어보면서 코드를 돌려보며 -> 틀린지 안틀린지를 확인해야 합니다.)

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 조용근님.

트리 문제에서 자주 겪는 어려움 중 하나가 노드 입력 순서에 대한 것입니다. 일반적으로 트리 구조에서는 부모 노드가 자식 노드보다 먼저 나오는 것이 보편적이지만, 모든 입력이 이러한 규칙을 따르지는 않으므로 주의가 필요합니다.

트리 입력 방식에서 착오가 일어나지 않게 하기 위해서는 부모-자식 관계를 명시적으로 저장하는 것이 중요합니다. 이를 위해서 다음과 같은 방법을 고려해 보세요:

1. 노드 저장 방식 변경: 노드를 입력받을 때마다 부모와 자식 간의 관계를 명시적으로 저장할 수 있도록 데이터를 구조화하는 것이 좋습니다. 예를 들어, 각 노드에 대한 인접 리스트를 생성하여, 어느 노드가 부모이고 어느 노드가 자식인지 추적할 수 있도록 합니다.

2. 유효성 검사: 입력을 받을 때마다, 해당 입력이 올바른 트리 구조를 형성할 수 있는지 확인하는 검사를 추가합니다. 이를테면, 사이클이 발생하지 않도록 하고 모든 노드가 연결되어 있는지 확인하는 과정이 필요합니다.

3. 기본 탐색 알고리즘 활용: 입력받은 트리 구조를 그래프로 변환하여 탐색 알고리즘(DFS/BFS)을 활용해 부모 자식 관계를 식별하는 방법도 있습니다. 이를 통해 모든 노드를 방문하며 트리 구조를 형성할 수 있는지도 체크할 수 있을 것입니다.

관련된 유사한 질문이 있는 게시물을 참조하여 더 나은 방법을 찾을 수 있습니다. 이러한 게시물에서는 사용자가 유사한 문제에 대해 어떻게 접근했는지를 확인할 수 있습니다:

1. 13244 tree 문제 질문
   
2. 2-R 1068 질문 드립니다.
   

이와 비슷한 내용을 탐색하며 해결 방안을 참조하시기 바랍니다. 해결 과정이 도움이 되셨으면 좋겠습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.