2019 KAKAO 코딩테스트 길 찾기 게임

https://programmers.co.kr/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임

 

 

세세한 조건을 따져가면서 그래프를 그리는 것은 구현상 힘들다고 판단했다. 그래서 다른 방법을 사용하였다.

 

첫째, 문제 조건에 따라 y값은 0~999 범위 내로 압축될 수 있다.
위 조건에 따라 좌표압축을 통해 y값을 변경해줬다. 이때, root(y값이 가장 큰 node)의 y 값은 0, 그다음 큰 값들은 1, ... 이런 식으로 변경하였다.

둘째, x 값 (node[1])으로 정렬하면 중위 탐색순서가 된다.

중위 탐색 순서와 각 node의 depth를 알게 되었으니, 구간을 분할하면서 child 를 구하면 된다.

 

import sys
sys.setrecursionlimit(10**6)

def solution(nodeinfo):
    answer = [[],[]]
            
    root = 0
    #좌표 압축
    y = [node[1] for node in nodeinfo]
    y.sort(reverse=True)
    depth = dict()
    d = 0
    for t in y:
        if t not in depth:
            depth[t] = d
            d += 1        
    for idx in range(len(nodeinfo)):
        nodeinfo[idx].append(idx+1)
        nodeinfo[idx][1] = depth[nodeinfo[idx][1]]
        #nodeinfo : [x, depth, num,]
        
    nodeinfo.sort() #중위 순회순
    for idx in range(len(nodeinfo)):
        if nodeinfo[idx][1] == 0:
            root = idx
            break
    
    #left : end가 parent
    #right : start가 parent
    def rec(start, end, depth, now):
        if start > end: return
        answer[0].append(nodeinfo[now][2])
        l = []
        for i in range(start, end+1):
            if(nodeinfo[i][1] == depth + 1):
                l.append(i)
        for i in l:
            if now < i:
                rec(now+1, end, depth+1, i)
            else:
                rec(start, now-1, depth+1, i)
        answer[1].append(nodeinfo[now][2])
    
    rec(0, len(nodeinfo)-1, 0, root)
    
    return answer

pythonic하게 짜면 좀 더 짧아질 것 같다.