[트리] 트리 문제에 대한 고찰, python

🤔 왜 떠올리지 못했을까?

사실 이 문제는 백준에서 먼저 본 것이 아니라 알고스팟 문제를 풀어보려다가 백준 문제도 있나 찾아보았다.

처음 보았을 때는 간단한 문제라고 생각했다, 그래서 재귀적으로 호출해 주면 되겠다라는 생각으로 무작정 문제에 달려들었다. 하지만 InOrder index와 PreOrder index들이 복잡해 지고, 꼬이고 생각이 많아지니 잘못되었다는 생각을 못하고 계속해서 시도해보게되었다. 으.. 될 거 같으면서도 계속 반복문이랑 재귀랑 꼬여서 시간만 낭비했다.. 진짜 뇌절한 것 같다...

또 작성하면서 생각난 것인데, PreOrder index를 자꾸 InOrder index 탐색하는 범위에 관련이 있다고 생각하는 바람에 계속해서 틀린 방법만 떠올린 것 같다. 둘을 아예 따로 생각하고 빼서 생각해봤으면 좋았을텐데 아쉽다.

일단 답지를 보기전에 내 생각은 for 문을 돌면서 PreOrder index를 기준으로 잡고 왼쪽 오른쪽 나누어서 재귀적으로 실행하는 것이었다. 실제로 어느정도 맞는 방법이었지만 Index를 세세하게 생각하지 못해서 계속해서 실수가 나왔고 불필요한 for문 안에 재귀함수가 들어 가면서 풀이가 점점 이상해지고 더러워졌다.. 너무 오래 붙잡고 있으니 집중도 더 안되었다.

사실 이런 특정 index를 기준으로 잡고 기저 사례 잡는 것이 정말 중요한데 자꾸 대충 맞겠지라는 추측과 함께 사용하느라 오늘 크게 혼난 것 같다. 진짜 앞으로는 정확하게 기저사례, 그리고 기준을 제대로 잡고 풀이를 해야겠다는 생각이 들었다.

🛍 비록 시간을 날렸지만...

비록 뇌절하면서 시간을 많이 소비하긴 했지만, 트리 순회에 대해서 조금 깊게 알게 된 것 같아서 그나마 다행이라고 위로하고 싶다. 처음에는 정말 PreOrder, InOrder 둘 만으로도 그래프를 그릴 수 있는지 의아하기도 했다. 덕분에 진짜 트리 순회에 대한 특징을 깊게 고민하게 된 것 같아서 좀 다행이라는 생각이 들었다.

PreOrder는 자기보다 오른쪽이 일단 자식인 것은 알겠지만, left child인지 right child인지 모른다. 그래서 결국 InOrder를 통해 봐야 하는 데, InOrder는 기준을 잡으면 누가 left child인지 right child인지 알 수 있지만 기준을 잡아줘야 함으로, 두 순회를 통해 그래프를 완성 할 수 있다는 것을 알게 되었다.

그리고 문제 관련 된 정보는 GeeksForGeeks를 참고했다. 설명이 잘 되어 있는 것 같아서 보고 이해하는 데에 쉬웠다.

https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

           A
         /   \
       /       \
     D B E     F C
  PreOrder index == 0

         A
       /   \
     /       \
    B         F C
   / \        
 /     \    
D       E 
PreOrder index == 1 ~ 3
보는 것과 같이 PreOrder index는 사실상 기준만 잡아주며 하나씩 증가만 하면 된다. 딱히 InOrder 순서와 관련이 없다.

특히 나는 InOrder에서 index찾는 for문 안에 재귀를 불러서 시간을 정말 많이 잡아먹었다. (이렇게 풀면 아예 풀 수 가 없었던 거 같다)
특정 index를 찾는 함수는 밖으로 빼는 것이 정말 깔끔하고 실수를 줄일 수 있겠다는 생각을 했다.

내가 짠 소스 코드는 여기에서 참고하면 된다. 사실 GeeksForGeeks를 많이 참고한 코드이다.

https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/ALGO_TRAVERSAL.py

참고로 이건 특이하게 알고스팟 TRAVERSAL 문제와 입출력이 아예 동일하다.
막상 블로그 글을 작성하고 나서 느끼는 것이지만 혼자 떠올리기 좀 힘들었을 것 같다는 생각도 든다. 😂