Hama Develop

프로그래머스-[2019카카오블라인드] 길찾기 게임, 파이썬

March 31, 2020

출처

길 찾기 게임

전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.

라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.

그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.

라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다. 모든 노드는 서로 다른 x값을 가진다. 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다. 자식 노드의 y 값은 항상 부모 노드보다 작다. 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다. 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다. 아래 예시를 확인해보자.

라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)

tree_3.png

이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다.

tree_4.png

위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.

전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7 다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다.

그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다.

이제 당신이 나설 때가 되었다.

곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때, 노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

제한사항

nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다. nodeinfo의 길이는 1 이상 10,000 이하이다. nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다. 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다. 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다. 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

입출력 예 |nodeinfo| result| |-|-| |[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]| [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] 입출력 예 설명 입출력 예 #1

문제에 주어진 예시와 같다.

풀이

주어진 인풋을 바탕으로 트리를 그릴 수 있는가가 핵심인 문제였다.

혼자 풀어보려 노력을 했으나 결국, 다른 다른 사람의 풀이를 보고서야 풀수 있었다.

정답률이 5%도 안되는 수준의 문제 였으니 틀릴만 했다고 스스로를 위로해 본다.

먼저 문제에서 말하고 있는 전위 순회와 후위순회가 무엇인지 알아보도록 하자.

둘 모두 노드를 탐색하는 방법이다.

전위 순회란, 부모 -> 왼쪽자식 -> 오른쪽 자식 순으로 순회를 하는 것을 의미한다.

부모에서 시작해서 왼쪽 자식을 방문하고 왼쪽 자식에 왼쪽 자식이 있으면 다시 그 왼쪽 자식을 방문한다. 빙문힐 왼쪽 자식이 없는 경우 오른쪽 자식을 방문한다. 그 뒤 부모의 부모 노드의 오른쪽 자식을 방문한다. 방문한 노드에 왼쪽 자식이 있으면 다시 왼쪽 자식을 먼저 방문한다…

이런식으로 모든 노드를 탐색할 때가지 반복하는 것이 전위 순회다.

후위 순회는 왼쪽자식 -> 오른쪽 자식 -> 부모 순으로 순회하는 것을 의미한다.

왼쪽 자식에서 시작해서 자신과 같은 부모를 가진 오른쪽 자식이 있으면 방문한다. (왼쪽 자식이 없으면 가장 왼쪽에 있는 오른쪽 자식 노드에서 시작한다.) 더 그 뒤 부모노드를 방문한다. 방문한 노드와 형제인 노드의 자식중 제일 왼쪽에 있는 자식을 방문한다. 그리고 위의 과정을 반복한다.

순회에 대한 더 자세한 설명은 이 블로그에서 잘 해 놓았다.

자, 이제 문제 풀이에 들어가 보자.

알고리즘문제는 코딩보다 생각이 훨씬 중요하다. 무턱대고 코딩을 시작하면 오히려 비효율 적인 경우가 많다.

문제를 풀기 위해서는 문제를 먼저 정의하고 문제를 작은 문제로 나누어 해결한 다음 합쳐야 한다.

나는 이 문제를 주어진 규칙에 따라 인풋값을 순회시키는 문제로 정의 하겠다.

위의 문제는 다시 작은 문제들로 나뉘어 질 수 있다.

주어진 규칙이 뭔지? 인풋값을 어떻게 순환 시키는지? 등으로 말이다.

주어진 규칙은 위에서 설명했다. 전위/후위 순회다. 이것에 대한 파악은 마쳤다.

인풋값은 어떻게 순회시킬 수 있을까?

이를 위해 인풋값이 무엇인지, 순회시키기 위해서 필요한 것이 뭔지를 생각해 보아야 한다.

먼저 인풋값은 인덱스+1 값을 노드 번호로 가지는 노드의 좌표들이다.

우리가 문제에서 출력해야 하는 것은 방문한 노드 번호들이다. 지금처럼 인덱스로 번호가 지정되어 있으면 순회를 시킨다고 해도 번호를 제대로 출력하기 어렵다. 따라서, 주어진 노드의 인덱스를 바탕으로 각 노드에게 번호를 부여해 주어야 한다.

아마 zip을 사용해서 번호를 부여해 주면 될 듯 하다.

이제 우리는 번호가 부여된 노드 주소들을 가지고 있다. 이걸 어떻게 순회 시킬까??

그래프 순회이니까 규칙에 따라 재귀적으로 함수를 구성하면 될 거 같다.

재귀 함수에 노드를 집어 넣으면, 재귀함수는 파라메터로 들어온 노드의 값중 가장뒤의 값을 정답에 이어 붙이는 역할을 하게 만들 것이다.

y좌표를 기준으로 큰게 앞으로, y좌표가 같을 때는 x좌표가 작은게 앞으로 오게 정렬을 하자. 이를통해 나중에 for문을 돌릴때 우리가 원하는 순서로 원소를 집어 넣을 수 있게 된다.

자 그럼, 재귀 함수에 넣기 좋도록 노드를 y좌표 기준으로 정렬하자.

순회는 재귀함수로 해야할 것 같은데 어떻게 재귀 함수를 써야 할까?

이제 이 문제의 핵심, 재귀함수를 구성하기 위한 고민을 해야 한다.

재귀함수 자체가 뭔가를 리턴하게 하면 생각이 너무 복잡해 질 것 같으니 재귀함수의 연산이 외부 변수에 영향을 미치도록 설계 해야 겠다.

외부 변수는 처럼 미리 선언하고 재귀함수가 들어오는 인풋들을 여기 뒤에 붙이는 식으로 작동하게 해야 한다.

preorder = list() 
postorder = list()

재귀 함수는 들어온 인풋을 preorder 와 postorder 에 골고루 붙이는 역할을 한다. 파라메터로 들어온 값을 리스트에 붙이고 그 다음 층에 있는 값들을 순회하면 재귀적으로 각 노드를 방문한다.

구체적으로는 한번 순회 할 때마다 다음 층으로 내려가야 한다.

전체 노드가 어떤 층에 있는지 구분점을 잡아 주어야 한다.

문제에 의하면 y 좌표가 노드의 레벨(높이)이 된다. y좌표에 의해서 부모자식 관계가 정의 되는 것이다.

0 부터 n 까지 y좌표가 차례대로 있고 이게 레벨이라면 부모 자식을 판별하기 쉽겠지만, 인풋은 그렇게 주어지지 않는다. 그저 높고 낮음만 주어질 뿐이다.

주어진 인풋에 들어 있는 y좌표들을 다 모아서 줄을 세우면 주어진 노드에 들어 있는 모든 y가 되고 이는 곧 레벨이 구분되는 지점이 된다

levels = sorted({i[2] for i in nodeinfo}, reverse = True)

위의 식을 통해서 노드를 구성하고 있는 레벨을 알아낼 수 있다.

이제 각 재귀 마다 다음 레벨로 깊어 지도록 재귀 함수를 수행하면된다.

주어진 노드리스트의 제일 뒤, 즉 y 값이 가장 큰 걸 정답에 붙인 뒤 왼쪽을 순회하는 재귀와 오른쪽을 순회하는 재귀를 만들어서 이어 붙인다.

(이 부분은 어떻게 더쉽게 설명하기가 너무 어려운점 양해 부탁드린다…)

def order(nodeList, level, curLevel):
    n = nodeList[:]
    cur = n.pop(0) # 리스트의 맨 앞 노드를 불러온다. 
    preorder.append(cur[0]) # 그걸 preorder에 붙인다.
    if n:
        for i in range(len(n)): # 남아 있는 리스트 중에서
            if n[i][1][1] == level[curLevel+1]: # 다음 레벨에 있는 노드인데,
                if n[i][1][0] < cur[1][0]: # x 값이 현재 노드보다 작으면, 왼쪽
                    order( [x for x in n if x[1][0] < cur[1][0]], level, curLevel + 1 ) #x값이 작은 노드를 모두 가지고 다시 재귀 함수 선언 
                else: # 보다 크면 오른쪽 
                    order( [x for x in n if x[1][0] > cur[1][0]], level, curLevel + 1 ) #x값이 더 큰 노드들을 가지고 재귀함수 선언
                    break # 오른쪽이 한번 나오면 중지 하는 이유 : 오른쪽이 나오는 순간 형제 노드 순회가 종료된 것이기 때문
    postorder.append(cur[0]) # 마지막에 postorder에 cur 를 붙여주면 후위 순회가 완성된다. 

그래서 전체 풀이는…

import sys
sys.setrecursionlimit(10**6) #이걸 안해주면 횟수제한에 걸려서 재귀가 막혀버림

preorder = list()
postorder = list()

def solution(nodeinfo):
    
    levels = sorted(list({x[1] for x in nodeinfo}), reverse=True) # 어떤 레벨이 있는지 파악 
    nodes = sorted(list(zip(range(1, len(nodeinfo)+1),nodeinfo) ), key= lambda x: (-x[1][1], x[1][0]))    #노드좌표와 인덱스를 서로 연결 해 줌 
    order(nodes, levels, 0)

    return [preorder, postorder]

def order(nodeList, levels, curLevel):
    n = nodeList[:]
    cur = n.pop(0)
    preorder.append(cur[0])
    if n:
        for i in range(len(n)):
            if n[i][1][1] == levels[curLevel+1]:
                if n[i][1][0] < cur[1][0]:
                    order([x for x in nodeList if x[1][0]< cur[1][0]], levels, curLevel+1)
                else:
                    order([x for x in nodeList if x[1][0]> cur[1][0]], levels, curLevel+1)
    postorder.append(cur[0])

이와 같다. 너무 어려운 문제였다…