코딩테스트

[Python] 프로그래머스 길 찾기 게임 Tree 자료형으로 풀기

코카멍멍 2023. 5. 13. 17:56
반응형

길찾기 게임

문제 설명

x, y 좌표로 이루어진 이진트리의 맵에서 전위 순회, 후위 순회 방식으로 순회한 노드의 번호들을 반환하는 문제입니다.

문제 해결방법

저는 이 문제를 해결하기 위해서 트리 자료구조를 만들어서 문제를 해결해보고자 했습니다.

트리 자료구조 만들기

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

우선 필드를 보면 x와 y좌표 자식 노드를 저장할 left, right와 부모노드를 가르키는 parent 필드로 구성하였습니다.

노드를 추가하는 방식

노드 추가하는 방식은 양방향 링크드 리스트와 유사하게 작성했습니다.
1번, 2번이 연결되어있는 상태에서 3번 노드가 추가 되면
3번 노드의 부모 노드와 1번 LEFT(자식 노드)를 연결 시키고 기존의 연결은 끊어주는 것입니다.
3번 노드와 2번 노드와도 동일합니다.

Node 삽입 메소드 작성하기

    def insert(self, node):
        # print('self :', self.x, self.y)
        # print('in node : ', node.x, node.y)
        if node.y < self.y: # 1. 생성한 노드 y값이 비교할 노드 y값 보다 클때
            # print('smaller')
            if node.x < self.x: # 1.1. 생성한 노드 x값이 비교할 노드 x 값 보다 클 때
                if self.left is None:  
                    self.left = node
                    node.parent = self
                    # print('left')
                else:
                    self.left.insert(node) #자식이 존재할 때 자식노드를 향해 insert() 메소드 실행
            else: # 1.2. 생성한 노드 x값이 비교할 노드 x 값 보다 작을 때
                if self.right is None:
                    self.right = node
                    node.parent = self
                    # print('right')
                else:
                    self.right.insert(node)
        else:  # 2. 생성할 노드 y값이 비교할 노드 y값 보다 작을 때
            # print('bigger')
            if node.x > self.x: # 2.1. 생성한 노드 x값이 비교할 노드 x 값 보다 클 때
                node.left = self  
                node.parent = self.parent  
                self.parent = node  
                # print('self left')
                if self.right is not None and self.right.x > node.x:
                    node.right = self.right
                    self.right.parent = node
                    self.right = None
                    # print(node.x, node.y, " left : right", self.right.x, self.right.y)

            else: # 2.2. 생성한 노드 x값이 비교할 노드 y 값 보다 작을 때
                node.right = self
                node.parent = self.parent
                self.parent = node
                # print('self right')
                if self.left is not None and self.left.x < node.x:
                    node.left = self.left
                    self.left.parent = node
                    self.left = None
        return

총 큰 굵직한 if문으로 보면
생성한 노드 : node
비교할 노드 : self

  1. 생성한 노드 y값이 비교할 노드 y값 보다 클때
    1.1. 생성한 노드 x값이 비교할 노드 x 값 보다 클 때
    1.2. 생성한 노드 x값이 비교할 노드 x 값 보다 작을 때
  2. 생성할 노드 y값이 비교할 노드 y값 보다 작을 때
    2.1. 생성한 노드 x값이 비교할 노드 x 값 보다 클 때
    2.2. 생성한 노드 x값이 비교할 노드 y 값 보다 작을 때

이렇게 4가지의 경우의 수를 처리해 주었습니다.

순회 방식

트리를 순회하는 방식에 대해서는 이진트리 전위, 중위, 후위 순회 에 설명했습니다.

전위순회

    def preorder(self, node, res):
        # print(node.x, node.y)
        res.append(node.value)
        if node.left is not None:
            node.preorder(node.left, res)
        if node.right is not None:
            node.preorder(node.right, res)

중위순회

    def inorder(self, node, res):
        if node.left is not None:
            node.inorder(node.left, res)
        # print(node.x, node.y)
        res.append(node.value)
        if node.right is not None:
            node.inorder(node.right, res)

후위순회

    def postorder(self, node, res):
        if node.left is not None:
            node.postorder(node.left, res)
        if node.right is not None:
            node.postorder(node.right, res)
        # print(node.x, node.y)
        res.append(node.value)

실행 함수

def solution(nodeinfo):
    answer = [[]]
    pre = []
    post = []
    for i, value in enumerate(nodeinfo):
        nodeinfo[i] = [value[0],value[1],i+1]
    nodeinfo.sort(key=lambda x: (-x[1], x[0]))
    node1 = Node(nodeinfo[0][0], nodeinfo[0][1], nodeinfo[0][2])
    for i in range(1, len(nodeinfo)):
        x, y, v = nodeinfo[i]
        node1.insert(Node(x, y, v))
    node1.preorder(node1, pre)
    node1.postorder(node1, post)
    return [pre, post]

이 코드에서 주의해야할 부분은 입력값 정렬입니다.

겪은 문제점

  • 입력값 정렬 및 인덱싱

이 예시를 보면 좋을 것 같습니다.

트리구조의 속성 중에 하나는 root 노드는 한개만 존재해야 한다는 점입니다.
1번, 2번, 3번 을 추가했을 때는 계속해서 root 노드가 한개만 존재합니다.
하지만 4번 노드를 추가할 때는 2번과 4번의 같은 레벨이면서 최상위 노드를 이루고 있습니다.
그렇기 때문에 최상위 부모 노드부터 최하위 자식 노드를 순서대로 정렬해서 노드를 추가할 필요가 있습니다.

  • 부모 노드 교체시 자식 노드 x값 비교

1번, 2번, 3번 노드를 삽입할 때는 전혀 문제가 발생하지 않습니다.
4번 노드를 추가할 때는 3번 노드가 4번 노드의 오른쪽에 존재합니다.
그렇기에 3번 노드를 4번 노드의 오른쪽에 붙혀줘야합니다.

전체 코드

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

    def insert(self, node):
        # print('self :', self.x, self.y)
        # print('in node : ', node.x, node.y)
        if node.y < self.y:
            # print('smaller')
            if node.x < self.x:
                if self.left is None:
                    self.left = node
                    node.parent = self
                    # print('left')
                else:
                    self.left.insert(node)
            else:
                if self.right is None:
                    self.right = node
                    node.parent = self
                    # print('right')
                else:
                    self.right.insert(node)
        else:  # 현재 들어온 노드가 해당 노드보다 클 때
            # print('bigger')
            if node.x > self.x:
                node.left = self  # 현재 노드 입력 노드의 자식 노드로 변경
                node.parent = self.parent  # 현재 노드의 부모 노드를 입력 노드의 부모로 저장
                self.parent = node  # 현재 노드의 부모 노드를 입력 노드로 변경
                # print('self left')
                if self.right is not None and self.right.x > node.x:
                    node.right = self.right
                    self.right.parent = node
                    self.right = None
                    # print(node.x, node.y, " left : right", self.right.x, self.right.y)

            else:
                node.right = self
                node.parent = self.parent
                self.parent = node
                # print('self right')
                if self.left is not None and self.left.x < node.x:
                    node.left = self.left
                    self.left.parent = node
                    self.left = None
        return

    def preorder(self, node, res):
        # print(node.x, node.y)
        res.append(node.value)
        if node.left is not None:
            node.preorder(node.left, res)
        if node.right is not None:
            node.preorder(node.right, res)

    def inorder(self, node, res):
        if node.left is not None:
            node.inorder(node.left, res)
        # print(node.x, node.y)
        res.append(node.value)
        if node.right is not None:
            node.inorder(node.right, res)

    def postorder(self, node, res):
        if node.left is not None:
            node.postorder(node.left, res)
        if node.right is not None:
            node.postorder(node.right, res)
        # print(node.x, node.y)
        res.append(node.value)


def solution(nodeinfo):
    answer = [[]]
    pre = []
    post = []
    for i, value in enumerate(nodeinfo):
        nodeinfo[i] = [value[0],value[1],i+1]
    nodeinfo.sort(key=lambda x: (-x[1], x[0]))
    node1 = Node(nodeinfo[0][0], nodeinfo[0][1], nodeinfo[0][2])
    for i in range(1, len(nodeinfo)):
        x, y, v = nodeinfo[i]
        node1.insert(Node(x, y, v))
    node1.preorder(node1, pre)
    node1.postorder(node1, post)
    return [pre, post]

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

전위, 중위, 순회 방법 게시글

반응형
저작자표시

'코딩테스트' 카테고리의 다른 글

[Python] 백준 1430 공격  (0) 2023.09.16
[ Python ] 프로그래머스 택배상자  (0) 2023.06.29
[Python] 프로그래머스 프렌즈 4블록  (1) 2023.05.15
[Python] 프로그래머스 양궁대회  (0) 2023.05.10
[Python] 프로그래머스 후보키  (0) 2023.05.07

'코딩테스트'의 다른글

  • 현재글[Python] 프로그래머스 길 찾기 게임 Tree 자료형으로 풀기

관련글

티스토리툴바