binarysearch tree
-
[프로그래머스] 길 찾기 게임문제 풀이 2020. 5. 30. 16:15
풀이)이진탐색트리를 구현하면 되는 문제이다. 풀이과정은 이러하다. 1. 각 node의 번호를 좌표 옆에 삽입시켜 준다. (탐색 시 노드 번호를 출력하기 위해서)2. 각 node들을 좌표순으로 정렬해준다. (원래 이진탐색트리는 삽입 순서에 따라 트리모양이 달라지지만, 이 문제에서는 (x,y)좌표 순으로 노드들이 이진트리를 구성하기 때문에 삽입순서가 중요하지 않다.좌표가 중요하다. y좌표가 높은 순, y좌표가 같다면 x좌표가 작은 순으로 나열한다.)3. 각 노드들로 이진탐색트리를 만들어 순회 경로를 출력한다. 전위순회는 나 자신 -> 왼쪽자식 ->오른쪽 자식 순이고 후위순회는 왼쪽자식 ->오른쪽자식 ->나 자신 순이다. 코드)#include #include #include #include using name..