[Algorithm] 여행경로, 등굣길

리쫑·2023년 2월 6일
0

Algorithm

목록 보기
10/16

여행경로

🤡여행경로 (Lv.3)

🤑풀이

import copy

def make_graph(tickets) :
    graph = {}
    # graph 생성
    for ticket in tickets :
        graph[ticket[0]] = graph.get(ticket[0], [])
        graph[ticket[0]].append([ticket[1], False])
    # graph 내 순서 정렬    
    for leave in graph :
        for i in range(0, 3)[::-1] :
            graph[leave] = sorted(graph[leave], key=lambda x : x[0][i])
    return graph
    

def dfs(leave, graph, path, L) :
    if len(answer) == 0 :
        if leave in graph :
            for idx, info in enumerate(graph[leave]) :
                arrive, visitied = info

                if not visitied :
                    n_graph, n_path = copy.deepcopy(graph), path.copy()
                    n_graph[leave][idx][1] = True
                    n_path.append(arrive)
                    if len(n_path) == L+1 :
                        answer.append(n_path)
                    else :
                        dfs(arrive, n_graph, n_path, L)

        
def solution(tickets) :
    global answer
    answer = []
    path = ["ICN"]
    graph = make_graph(tickets)
    dfs("ICN", graph, path, len(tickets))
    return answer[0]

👩‍🏫 아이디어

  • make graph함수를 통해 이동경로를 알파벳 순서대로 정렬시킨 graph 생성
  • DFS를 사용하여 모든 티켓을 사용하는 경로 탐색.
  • 이동경로(path)와 티켓정보(graph)를 deepcopy 하여 경로와 잔여 티켓 정보를 메모리에 넘겨주어 dfs의 "깊이 우선 탐색" 알고리즘을 "깊이 이동경로 탐색" 알고리즘으로 변환.

등굣길

🤡등굣길 (Lv.3)

🤑풀이

def solution(m, n, puddles):
    load = [[1 if (i==0 and j==0) else 0 for i in range(n)] for j in range(m)]
    for i, j in puddles :
        load[i-1][j-1] = -1
    
    for i in range(m) :
        for j in range(n) :
            if load[i][j] == -1 : 
                continue
            else :
                load[i][j] += load[i][j-1] if j>0 and load[i][j-1] != -1 else 0
                load[i][j] += load[i-1][j] if i >0 and load[i-1][j] != -1 else 0

    return load[m-1][n-1]%1000000007

👩‍🏫 아이디어

  • Dynamic Programming, 점화식 작성
profile
AI, Data Scientist 취업 준비생 입니다. 공부한 내용을 포스팅하고자 합니다. 방문해주셔서 감사합니다

0개의 댓글