dfs 풀이
answer= []
def solution(tickets):
global answer
start =[]
N = len(tickets)
for i in range(N):
if tickets[i][0] == "ICN":
for j in range(N):
if j != i and tickets[i][1] == tickets[j][0]:
start.append((tickets[i][1], i))
break
start.sort(key = lambda x:x[0])
startidx = start[0][1]
visited = [startidx]
cur = tickets[startidx][1]
ans = [tickets[startidx][0], tickets[startidx][1]]
dfs(startidx, tickets, N, visited, cur, ans )
return answer
def dfs(startidx, tickets, N, visited, cur ,ans):
global answer
if len(ans) == (N+1):
if len(answer) == 0:
answer = ans.copy()
elif len(answer) != 0:
for i in range(N+1):
if ans[i] < answer[i]:
answer = ans.copy()
return
elif ans[i] == answer[i]:
continue
elif ans[i] > answer[i]:
return
return
for i in range(N):
if i not in visited and tickets[i][0] == cur:
ans.append(tickets[i][1])
visited.append(i)
dfs(startidx, tickets, N, visited, tickets[i][1], ans)
ans.pop()
visited.pop()728x90
'코테 > 프로그래머스' 카테고리의 다른 글
| 프로그래머스 자물쇠와 열쇠 (0) | 2023.01.08 |
|---|---|
| 프로그래머스 문자열 압축 (0) | 2023.01.08 |
| 프로그래머스 단어 변환 (0) | 2022.12.28 |
| 프로그래머스 베스트앨범 (0) | 2022.12.28 |
| 프로그래머스 위장 (0) | 2022.12.28 |
