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

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 길 찾기 게임

새로 알게된 것들

1. 두 서브트리로 나눌 때 이분탐색을 하면 되겠다는 생각을 했는데 모듈이름이 생각나지 않았다. 금붕어도 아니고... 그리고 검색을 통해 bisect모듈을 알아낸 뒤에도 bisect.bisect_left()이 메서드에 key를 넣을 수 없다는 것을 알게 되었다. 리스트에 순수하게 하나의 자료형으로된 데이터만 이분탐색을 할 수 있고 만약 하고 싶다면 좀 복잡하게 구해야 했다.

2. 프로그래머스에서 문제를 풀면 유난히 런타임에러가 종종 나는 경우가 있었는데 대부분 재귀를 사용하여 발생한 에러였다. 그래서 그때마다 재귀말고 반복문을 이용해 해결하였다. 이번 문제또한 테스트6,7번에서 런타임에러가나 질문하기에서 검색해본 결과 재귀의 깊이를 더 늘릴 수 있는 방법이 있다는 것을 알게 되었다. 이 방법으로 저번에 런타임에러로 못 푼 문제를 다시 제출해보았더니 통과하였다!!!!

import sys
sys.setrecursionlimit(10**6)

위의 코드를 넣어 재귀의 limit를 늘려주면 앞으로 재귀로 문제를 해결할 수 있을 것 같다.

풀이

카카오 문제답게 완전 구현문제였다.

1. 노드의 인덱스를 노드의 x, y좌표와 함께 리스트에 넣어 정렬해도 어떤 인덱스의 노드인지 확인할 수 있게 만든다.

2. 주어진 노드들 중에서 y좌표가 가장 큰 노드를 반환하는 메서드를 작성한다.

3. x좌표로 정렬된 노드들 중에서 주어진 y좌표에 의해 두 그룹의 노드들로 나누어 반환한다.

4. make_tree() 메서드를 재귀로 구현하여 잎노드까지 tree를 만들 수 있도록 하였다. 이때 전체 tree에서 루트노드가 무엇인지 초기화해준다. 나중에 전위, 후위 탐색을 할 때 이용한다.

5. 주어진 노드들 중에서 루트노드를 찾고 루트노드를 기준으로 나머지 노드들을 두 그룹으로 만든다.

6. 나눈 두 그룹도 다시 make_tree()로 tree를 만들어 나간다.

7. 만약 더 이상 노드가 없다면 바로 반환하여 빠져나온다.

8. make_tree()로 만들어진 tree로 전위탐색과 후위탐색을 하여 answer에 넣어 반환해준다.

코드

import sys
sys.setrecursionlimit(10**6) # 파이썬 재귀 limit 늘려주는 코드

# y좌표가 가장 큰 노드
def find_root(nodes):
    return max(nodes, key=lambda x:x[2])

# 루트를 중심으로(x좌표) 두 노드로 나눔, nodes는 x좌표로 정렬된 리스트
def divide_nodes(nodes, y):
    for i, node in enumerate(nodes):
        if y == node[2]:
            # root를 제외하고 두 리스트로 분리
            return nodes[:i], nodes[i + 1:]

def solution(nodeinfo):
    nodes = [(i + 1, x, y) for i, (x, y) in enumerate(nodeinfo)]
    root, tree = -1, {}
    
    def make_tree(nodes, p):
        if not nodes: return
        i, x, y = find_root(nodes)
        if p == -1:
            nonlocal root
            root = i
        else:
            tree[p].append(i)
        tree[i] = []
        x_nodes = sorted(nodes, key=lambda x:x[1])
        left_nodes, right_nodes = divide_nodes(x_nodes, y)
        make_tree(left_nodes, i)
        make_tree(right_nodes, i)
    
    make_tree(nodes, -1)
    
    pre_list = []
    def preorder(parent):
        pre_list.append(parent)
        for child in tree[parent]:
            preorder(child)
    
    post_list = []
    def postorder(parent):
        for child in tree[parent]:
            postorder(child)
        post_list.append(parent)
    
    preorder(root)
    postorder(root)
    
    answer = [pre_list, post_list]
    return answer

다른 사람 풀이를 보며 알게 된 점

다른 사람 풀이를 보고 많이 코드를 리팩토링하였다. 문제를 풀때는 보이지 않는 것들이 다른 사람 코드를 보면서 많은 것을 보였다. 먼저 tree를 직접 구해 전위탐색과 후위탐색을 하였지만 tree를 구하는 과정에서 두 탐색을 모두 할 수 있다. 문제 풀면서 가능할거 같다는 생각을 했지만 푸는 게 먼저라는 마음이 앞서서 고치지 못했다. tree를 구하는 과정에서 두 탐색을 함으로써 tree 또한 직접 구할 필요가 없다는 것을 깨달았다.

수정한 코드

import sys
sys.setrecursionlimit(10**6) # 파이썬 재귀 limit 늘려주는 코드

def find_root(nodes):
    return max(nodes, key=lambda x:x[2])

def divide_nodes(nodes, y):
    for i, node in enumerate(nodes):
        if y == node[2]:
            return nodes[:i], nodes[i + 1:]

def solution(nodeinfo):
    nodes = [(i + 1, x, y) for i, (x, y) in enumerate(nodeinfo)]
    pre_list, post_list = [], []
    
    def make_tree(nodes):
        if not nodes: return
        i, x, y = find_root(nodes)
        pre_list.append(i)
        x_nodes = sorted(nodes, key=lambda x:x[1])
        left_nodes, right_nodes = divide_nodes(x_nodes, y)
        make_tree(left_nodes)
        make_tree(right_nodes)
        post_list.append(i)
    
    make_tree(nodes)
    
    answer = [pre_list, post_list]
    return answer