[프로그래머스][트리] 길 찾기 게임

문제

트리를 구성하는 노드의 x, y 좌표들이 주어질 때 규칙에 맞게 이진트리를 그리고 전위 순회와 후위 순회 결과를 출력하시오.

문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/42892)

풀이

이 문제는 지난번 하반기 채용 당시 풀어야했던 문젠데 못 풀었던! 문제였습니다. 오늘은 오랜만에 프로그래머스에 들어갔다가 이 문제를 골랐는데 풀 수 있는 방법이 떠올라서 풀었습니다! 처음에 이 문제를 봤을 때는 좌표가 x, y로 주어지는데 이진트리로 표현하기 위한 방법이 떠오르지않아서 못풀었는데 오늘은 우선순위큐를 이용하면 풀 수 있겠다는 생각이 들었습니다. y좌표가 높을수록, x좌표가 작을수록 우선순위큐를 만들어주면 가장 위에서 부터 차례대로 각 레벨안에서 노드들의 순서가 정리가 됩니다. 예시에 있는 좌표를 이용하면 우선순위 큐에 들어있는 순서는 7, 4, 2, 6, 1, 3, 9, 8, 5가 됩니다. 이렇게 되면 큐에서 하나씩 빼며 root에서부터 자식노드들을 만들어줍니다. 먼저 나오는 노드들이 무조건 다음에 나오는 노드들의 부모노드가 될 수 밖에 없으므로 하나씩 빼며 자신의 자리들을 찾아 갑니다. 자리를 찾기 위해서는 x좌표를 통해서 더 작을 경우 왼쪽으로 더 클 경우 오른쪽으로 붙여주면 됩니다.(이미 큐 안에서 y좌표에 의해 차례가 정렬되어 있으므로 y좌표는 이후에 필요하지 않습니다.) 이렇게 트리를 만들게 되면 전위 순회와 후위 순회를 해주면 끝입니다! 몇개월만에 다시 읽어보고 푸는 문제인데 못풀었었는데 오늘은 1시간 이내로 푼 것 같아서 뿌듯합니다!

코드

https://github.com/kswim/Algorithm/blob/master/etc/42892.cpp