[Programmers] 길 찾기 게임

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 

문제에서 주어진 조건 "모든 노드는 서로 다른 x값을 가진다."이 핵심인 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 nodeinfo 이차원 벡터의 각 벡터에 노드 번호를 부여합니다.

2. x 좌표 기준으로 오름차순 정렬을 진행하고

3. drawTree 메서드를 통해 이진트리를 생성해줍니다.

3.1 x 좌표 기준으로 오름차순 정렬이 되어있으므로 y 좌표가 제일 큰 노드가 해당 서브 트리의 root이고 루트 노드를 기준으로 왼쪽, 오른쪽 서브 트리를 연결해줍니다.

3.2 3.1번의 방식대로 drawTree 재귀함수를 호출하여 이진트리를 생성해줍니다.

4. 3번에서 생성한 이진트리를 기준으로 전위 순회, 후위 순회를 진행합니다.

5. 4번에서 구한 전위 순회, 후위 순회의 결과를 answer 벡터에 추가하고 answer를 반환합니다.

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~