알고리즘/programmers

[Programmers] 길 찾기 게임

꾸준함. 2022. 7. 26. 04:33

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제에서 주어진 조건 "모든 노드는 서로 다른 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

 

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

반응형