[프로그래머스-파이썬] 연습문제(LV3) : 길 찾기 게임

<문제출처>

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

프로그래머스

 

<체크포인트>

시간	쉽게해결	1시간이내	1시간 이상 or 몇 일 걸림	솔루션 보고 해결
체감 난이도	하	중	상	최상
이해도	완벽히이해	다소 헷갈리는 부분있음	이해못함
덧붙일 말

 

 

<고민 끄적끄적>

문제를 처음 봤을 때 두 가지를 고민했다.

1. 연결노드 그래프를 구한다음에 전위, 후위를 할 것인가.
2. (x, y)의 좌표값을 정렬하고 그 관계를 이용해서 전위, 후위를 바로 구할 것인가.

이진트리 탐색의 경우 이전에 풀었을 때 정석은 항상 연결트리를 먼저 깔끔하게 구하면은 전위, 후위탐색은 문제도 아니어서 먼저 연결트리를 구하려고 해 봤다. 그런데 트리표현방식이 좌표(x, y)로 표현되어 있어서 먼가 바로 연결리스트로 만들 방법이 생각나지 않았다.

그래서 두번째 방법으로 x값에 따라 좌우가 나뉘기 때문에 x값으로 정렬한 후 분할정복 방식을 통해서 왼쪽 서브트리, 오른쪽 서브트리에 접근하기로 하였다.

이방식으로 하면은 분할정복을 함과 동시에 전위, 후위순위의 기록을 바로 남길 수 있기 때문에 구현하다 보니 이방식으로 하면 쉽게 풀리는구나라고 느꼈다.

 

 

최종코드

import sys
sys.setrecursionlimit(1000000)
'''
노드 1 ~ n (10000)
전위순회 - 후위순회를 구하라

분할정복을 통해서 규칙을 찾자

'''
ans1 = [] # 전위
ans2 = [] # 후위

# [(1, 3, 6), (2, 2, 9), (3, 5, 4), (5, 3, 1), (6, 1, 5), (7, 2, 8), (8, 6, 7), (11, 5, 2), (13, 3, 3)]
def func(start, end, s):
    if end == start:
        ans1.append(s[end][2])
        ans2.append(s[end][2])
        return
    if end < start:
        return
    
    max_v = s[start][1]
    max_idx = start
    for i in range(start, end + 1):
        if max_v < s[i][1]:
            max_v = s[i][1]
            max_idx = i
    
    ans1.append(s[max_idx][2])
    func(start, max_idx-1, s)
    func(max_idx + 1, end, s)
    ans2.append(s[max_idx][2])


def solution(nodeinfo):
    s = []
    for i, data in enumerate(nodeinfo):
        s.append((data[0], data[1], i + 1))          
    s.sort(key = lambda x : x[0])
    
    func(0, len(nodeinfo)-1, s)

    
    ans = []
    ans.append(ans1)
    ans.append(ans2)
    
    return ans

-> 분할정복에서 재귀방식을 사용하기 때문에 python에서는 setrecursionlimit값을 주는것을 잊지 말자!