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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

주어진 노드의 정보들을 이용하여 트리를 만들어내려 하였습니다.

그러나 트리를 만드는 과정에 다소 조건이 많았기에, 트리를 생성하지 않고 이진트리의 순회하는 방식의 특징을 이용하였습니다.

 

순회를 할때 현재 노드를 중심으로 하여 왼쪽 자식 노드와 오른쪽 자식 노드를 구하여 순회를 하였습니다.

2) 알고리즘

• 트리

3) 풀이 코드

사용 언어 - Python

import sys
sys.setrecursionlimit(10000)

def solution(nodeinfo):
    answer = [[], []]                   # 전위 순회, 후위 순회

    nodeinfo = list(sorted(enumerate(nodeinfo, start=1), key=lambda x: (x[1][1], x[1][0])))     # 루트 노드를 찾기 위해 정렬

    def order(nodes: list):                 # 트리의 순회
        if not nodes:                       # 노드가 없으면 종료
            return

        left_nodes, right_nodes = [], []    # 왼쪽, 오른쪽 자식 노드들
        node = nodes.pop()                  # 현재 노드의 정보 (부모 노드)

        for n in nodes:                     # 노드들의 정보들을 확인
            if n[1][0] < node[1][0]:        # 부모 노드보다 왼쪽에 있으면, 왼쪽 자식 노드에 추가
                left_nodes.append(n)
            else:                           # 오른쪽에 있으면 오른쪽 자식 노드에 추가
                right_nodes.append(n)

        answer[0].append(node[0])           # 전위 순회
        order(left_nodes)                   # 왼쪽, 오른쪽 자식 노드들 재귀하여 탐색
        order(right_nodes)
        answer[1].append(node[0])           # 후위 순회

    order(nodeinfo)                         # 출력

    return answer

print(solution([[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]))

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다