여행경로
🤡여행경로 (Lv.3)
🤑풀이
import copy
def make_graph(tickets) :
graph = {}
for ticket in tickets :
graph[ticket[0]] = graph.get(ticket[0], [])
graph[ticket[0]].append([ticket[1], False])
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, 점화식 작성