[프로그래머스/파이썬] 길 찾기 게임(42892) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 길 찾기 게임(42892)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

노드 좌표 정보로 이진트리를 구성한 뒤, 전위 순회와 후위 순회 결과를 구하는 문제입니다.

코드

import sys

sys.setrecursionlimit(10_000)

class Node:
    def __init__(self, no, x, y, level = 0, parent = None, left = None, right = None):
        self.no = no
        self.x = x
        self.y = y
        self.level = level
        self.parent = parent
        self.left = left
        self.right = right

    def __str__(self):
        parent = left = right = 'None'
        try: parent = self.parent.no
        except:pass
        try: left = self.left.no
        except:pass
        try: right = self.right.no
        except:pass
        
        return f'No.{self.no} - x: {self.x}, y: {self.y}, lvl: {self.level}, parent: {parent}, left:{left}, right:{right}'

def solution(nodeinfo):
    nodes = []
    n = len(nodeinfo)
    
    for i in range(n):
        nodes.append((i+1, nodeinfo[i][0], nodeinfo[i][1]))

    nodes.sort(key = lambda x:(-x[2], x[1]))
    #print(nodes)

    tree = Node(*nodes[0])
    tree_nodes = [tree]

    parent_start = parent_end = 0
    for i in range(1, n):
        level = tree_nodes[-1].level
        if tree_nodes[-1].y > nodes[i][2]:
            parent_start = parent_end
            parent_end = i
            level += 1

        # 시간초과 해결법: 부모의 레벨을 특정시킨 후, 해당 레벨대의 인덱스만 검색
        for j in range(parent_start, parent_end):
            if nodes[i][1] < nodes[j][1] and\
               tree_nodes[j].left is None and\
               tree_nodes[j].level == level - 1 :
                
                check_x, tmp = True, tree_nodes[j]
                while True:
                    x = tmp.x
                    tmp = tmp.parent
                    if tmp == None: break
                    sub_dir = 'L' if x < tmp.x else 'R'
                    
                    if sub_dir == 'L' and nodes[i][1] >= tmp.x or\
                       sub_dir == 'R' and nodes[i][1] <= tmp.x:
                        check_x = False
                        break
                    
                if check_x:
                    tree_nodes.append(Node(*nodes[i]))
                    tree_nodes[-1].level = level
                    tree_nodes[-1].parent = tree_nodes[j]
                    tree_nodes[j].left = tree_nodes[-1]
                    break
                
            elif nodes[i][1] > nodes[j][1] and\
                 tree_nodes[j].right is None and\
                 tree_nodes[j].level == level - 1 :
                
                check_x, tmp = True, tree_nodes[j]
                while True:
                    x = tmp.x
                    tmp = tmp.parent
                    if tmp == None: break
                    sub_dir = 'L' if x < tmp.x else 'R'
                    
                    if sub_dir == 'L' and nodes[i][1] >= tmp.x or\
                       sub_dir == 'R' and nodes[i][1] <= tmp.x:
                        check_x = False
                        break
                    
                if check_x:
                    tree_nodes.append(Node(*nodes[i]))
                    tree_nodes[-1].level = level
                    tree_nodes[-1].parent = tree_nodes[j]
                    tree_nodes[j].right = tree_nodes[-1]
                    break

##    print(*map(str,tree_nodes),sep='\n')

    answer = [[], []]

    preorder_traversal(tree, answer[0])
    postorder_traversal(tree, answer[1])

    return answer

def preorder_traversal(tree, result):
    result.append(tree.no)
    if tree.left is not None: preorder_traversal(tree.left, result)
    if tree.right is not None: preorder_traversal(tree.right, result)
    
def postorder_traversal(tree, result):
    if tree.left is not None: postorder_traversal(tree.left, result)
    if tree.right is not None: postorder_traversal(tree.right, result)
    result.append(tree.no)
    

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

설명

노드를 y 내림차순, x 오름차순으로 정렬해서 위 레벨부터 순서대로 트리에 배치합니다.

트리 구성 후:

• 전위 순회(root-left-right)
• 후위 순회(left-right-root)

결과를 각각 리스트로 반환합니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---