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

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

프로그래머스

해당 문제를 풀기 위하서는 '이진' 트리라는 개념을 알아야한다.

물론 추후에 필자가 자료구조 카테고리에 작성할 내용이지만 간단히 설명하자면 다음과 같다.

'이진' 말 그대로 2개를 의미한다.

맨 위에 해당하는 최대 한 개의 노드의 아래에 최대 두 개의 노드가 이어져 있는 것이다.

그 노드에도 역시 각각 최대 두 개의 노드가 이어진 것을 이진 트리라고 한다. (다음에 그림으로 보다 자세하게 설명드릴게요)

위의 노드를 부모 노드라고 하고 아래의 노드를 자식 노드라고 한다.

즉 이진 트리는 하나의 부모 노드에 최대 두 개의 자식 노드가 있다는 것이다.

그리고 문제에서 요구하는 전위 순회와 후위 순회는 간단히 설명해서 첫 노드에서 왼쪽 자식노드부터 DFS 탐색을 했을 때, 그 값을 먼저 읽고 탐색을 하느냐 혹은 탐색을 하고 그 값을 읽느냐의 차이이다.

 

코드를 작성하기 위한 순서는 다음과 같다.

1. 노드의 갯수가 만 개 이하이므로 최대 재귀 횟수를 확장한다.

2. 문제에서 노드의 좌표만 나와있고 노드의 값이 나와있지 않기 때문에 따로 값을 넣어준다.

3. 문제의 조건에서 y값이 클수록 부모 노드이고 y값이 같으면 x값이 작은 쪽이 왼쪽에 위치하라고 했으므로 y값에 따라서 우선적으로 내림차순 정렬을 하고 x값에 따라서 오름차순 정렬을 해준다.

4. 전위 순회를 하는 재귀 함수 preorder 함수를 만들어준다.

5. 후위 순회를 하는 재귀 함수 postorder 함수를 만들어준다.

6. 두 순회를 하면서 담긴 값을 반환한다.

 

import sys #1번
sys.setrecursionlimit(10**9)

def preorder(nodeinfo, pre): #4번
    left = [] #해당 부모 노드의 왼쪽에 위치하는 leftchild이다.
    right = [] #해당 부모 노드의 오른쪽에 위치하는 rightchild이다.
    node = nodeinfo[0] #부모 노드는 y값이 가장 큰 노드이다.
    for i in range(1, len(nodeinfo)):
        if node[0] > nodeinfo[i][0]: #부모 노드보다 x 좌표 값이 작으면 왼쪽에 위치해야한다.
            left.append(nodeinfo[i])
        else: #부모 노드보다 x 좌표 값이 크면 오른쪽에 위치해야한다.
            right.append(nodeinfo[i])
    pre.append(node[2]) #전위 순회이므로 재귀호출을 하기 전에 해당 노드의 값을 넣어준다.
    if left: #leftchild가 있을 경우에 왼쪽에서부터 재귀호출을 해준다.
        preorder(left, pre)
    if right: #왼쪽에서의 재귀호출이 끝난 후에 rightchild가 있을 경우에 오른쪽에서의 재귀호출을 해준다.
        preorder(right, pre)
        
def postorder(nodeinfo, post): #5번 : 전위 순회와 거의 동일하다.
    node = nodeinfo[0]
    left = []
    right = []
    for i in range(1, len(nodeinfo)):
        if node[0] > nodeinfo[i][0]:
            left.append(nodeinfo[i])
        else:
            right.append(nodeinfo[i])
    if left:
        postorder(left, post)
    if right:
        postorder(right, post)
    post.append(node[2]) #후위 순회는 좌, 우의 모든 재귀호출이 끝났을 때, 해당 노드의 값을 넣어준다.

def solution(nodeinfo):
    pre = []
    post = []
    
    for i in range(len(nodeinfo)): #2번
        nodeinfo[i].append(i+1)
    nodeinfo.sort(key = lambda x:(-x[1], x[0])) #3번
    
    preorder(nodeinfo, pre)
    postorder(nodeinfo, post)
    
    return [pre, post] #6번

 

어제는 연결리스트를 class 선언 없이 딕셔너리를 통해 구현하는 법을 배웠고 오늘은 이진 트리를 class 선언 없이 전위, 후위 순회를 구현하였다.

정석적으로는 class를 선언하는 것이 맞지만, 해당 문제는 전위, 후위 순회가 문제에서 요구하는 답이었기에 다음과 같은 방법을 사용할 수 있었다.

역시 문제가 요구하는 것이 무엇인지 먼저 파악하는 일이 조금 더 효율적인 코드를 작성하는 데 도움을 주는 것 같다.

(문제를 풀면서 자료구조 응용 때, 낑낑거리면서 과제를 하던 기억이 나서 꽤나 재밌기도 하고 기분이 묘했어요. 이런 느낀점을 적으면 안되긴 하지만 그 당시에는 좀 많이 힘들었던 기억이 나네요. 이쪽 분야가 적성에 맞지 않아서 뒤쳐지면 어떻게 해야하나 걱정도 많이 하고 그만둘까하는 생각도 많았지만 그래도 꾸준히 하니까 어느정도의 난이도는 해결할 수 있게 되었네요. 열심히 하면 나중에는 어려웠던 일이 평범해지는 건 어딜가나 다 똑같나봐요. 그냥 갑자기 기뻐서 이렇게 길게 작성해봅니다. 여러분도 포기하지 마요.)