지난 주에는 트리를 직접 코드로 구현을 해보았는데, 사실 트리를 직접 만들어 보는 것도 중요하지만 이런 자료구조를 탐색하는 방법도 굉장히 중요하다. 실제로 우리가 코딩 테스트에서 마주하는 문제는 탐색에 대한 부분이기 때문이다. 이 탐색에도 여러 방법들이 있는데 오늘은 그런 방법을 정리해 볼 생각이다.
중위 순회
중위 순회(In-order traversal)는 왼쪽 자식 노드, 나(Root Node), 오른쪽 자식 노드 순으로 방문을 하게 된다. 즉 나를 중간에 방문하기 때문에 중위 순회라고 생각하면 기억하기 편하다. 아래 예시 트리가 있다.
중위 순회에서는 예시 코드를 다음과 같은 순서로 탐색한다. (2가 두 개인 관계로 leaf node를 2'로 표현)
2' 👉 7 👉 5 👉 6 👉 11 👉 2 👉 5 👉 4 👉 9
내가 트리가 되었다고 생각을 하고 순서에 대한 상황극을 해보자.
2: 자 지금부터 중위 순회를 해보겠어요. 보자, 일단 중위 순회는 왼쪽 자식 노드, 그리고 나, 마지막에 오른쪽 자식 노드이니까 7, 너부터 한 번 확인해 봐.
7: 네, 아버지. 2'야. 할아버지 말씀 잘 들었지? 왼쪽 자식 노드인 네가 첫 순서란다.
2': 예. 제가 첫 번째군요!
7: 그래 그리고 내가 두 번째구나. 세 번째는 오른쪽 자식, 6아. 너가 이어서 하거라.
6: 예, 아버지. 근데 저는 두 자식이 있는데 어떻게 하죠?
7: 아버지가 한대로, 왼쪽 손자 5를 먼저 하고 그리고 너, 마지막에 오른쪽 손자 11을 하면 되겠구나.
5: 할아버지! 그러면 제가 세 번째인가요?
7: 그렇지!
6: 아, 그러면 제가 네 번째가 되겠군요!
11: 아빠, 저는 그럼 다섯 번째에요.
이런 식으로 가는 것이다. 정말 순서를 딱딱 지켜서 해보면 크게 헷갈리지 않는다.
전위 순회
중위 순회(Pre-order traversal)는 내가 가운데 가는 방법이니 전위 순회는 바로 내가 가장 먼저 나온다는 것을 알 수 있다. 즉 나, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 탐색을 한다. 이 방법을 위 예시에 그대로 적용시켜 보자.
2 👉 7 👉 2' 👉 6 👉 5 👉 11 👉 5 👉 9 👉 4
후위 순회
후위 순회(Post-order traversal)는 내가 가장 마지막에 나오는 방법으로, 왼쪽 노드, 오른쪽 노드, 마지막에 내 차례이다. 이 방법을 위 예시에 적용시켜 보도록 하자.
2' 👉 5 👉 11 👉 6 👉 7 👉 4 👉 9 👉 5 👉 2
레벨 순회
레벨 순회(Level-order traversal)는 우리가 익히 들어 본 BFS(Breadth First Search)를 말한다. 같은 레벨에 있는 노드들을 먼저 순회하는 방법이다. 이 방법을 위 예시에 적용시켜 보자.
2 👉 7 👉 5 👉 2' 👉 6 👉 9 👉 5 👉 11 👉 4
각 방법에 적합한 자료구조
첫 세 가지 방법은 Leaf node까지 찍고 올라오는 형태가 되기 때문에 DFS(Depth First Search) 방법이라고 할 수 있다. 그렇기 때문에 스택를 이용하면 된다. 때에 따라서는 재귀를 이용해서 이를 구현할 수 있을 것이다.
하지만 레벨 순회는 차례대로 처리를 해주어야 하기 때문에, 큐를 이용해서 먼저 들어온 것 처리하고 다음 레벨 노드를 후 순위로 등록해 주고 그 다음 같은 레벨 노드를 탐색하고 동일하게 그 자식 노드를 후 순위로 등록해 주면서 레벨 단위로 탐색을 해 나간다.
마치며
이번 주는 지난 주의 트리 공부의 연장선상이었다. 문제를 직접 풀어보면서 '이게 DFS구나, 이래서 스택과 재귀를 쓴다는 거구나!', '이게 BFS구나, 이래서 큐를 사용하구나!' 하는 생각을 참 많이 했다. 물론 두 문제 다 내 머리로 한 번에 풀 수 없어서 검색의 힘을 빌렸지만 해당 코드를 이해하는 것도 트리 문제가 처음인 내겐 힘들었다. 그래도 이해를 하는 순간순간이 참 즐거웠다.
자료구조 공부는 대부분 이런 거 같다. '왜 코드가 이렇게 되는거지?' 싶다가도 이해를 하는 순간 '만든 사람 진짜 천재 아냐?' 하는 생각과 함께 기쁨의 박수를 치게 된다. 이번에도 그랬다. 특히나 DFS는 금방 이해했지만 BFS는 진짜 쉽지 않았다. 그래도 이해를 하고 나니 이런 이유 때문에 큐를 쓴다는 것을 확실하게 이해하게 되었다.
아직 갈 길이 먼 만큼 얼른 복습하고 다음 문제들을 풀어보면서 트리에 더 빠져들어 봐야겠다.
