강의
"깊이 우선 탐색"은 한 정점에서 인접하고 아직 방문하지 않은 모든 정점을 방문할 때, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝내고 다음 정점으로 이동하는 알고리즘 입니다.
"너비 우선 탐색"은 한 정점에서 인접하고 아직 방문하지 않은 모든 정점을 방문할 때, 방문한 각 인접 정점을 기준으로 방문한 순서에 따라 너비 우선 탐색을 행하는 알고리즘 입니다.
Step 7-3: 풀어서 내 것으로 만들자! 여행 경로
⭐ 힌트 풀이 : stack과 DFS를 이용하여 푸는 문제!
def solution(tickets):
routes = {}
for t in tickets:
routes[t[0]] = routes.get(t[0], []) + [t[1]]
for r in routes:
routes[r].sort(reverse = True)
visited = ["ICN"]
path = []
while len(visited) > 0:
top = visited[-1]
if top not in routes or len(routes[top]) == 0:
path.append(visited.pop())
else:
visited.append(routes[top][-1])
routes[top] = routes[top][:-1]
return path[::-1]
'데브코스 TIL > 자료구조, 알고리즘' 카테고리의 다른 글
Step 6: 동적계획법(Dynamic Programming) 대표 문제 풀이: N으로 표현 (0) | 2023.10.20 |
---|---|
Step 5: 힙(Heap) 대표 문제 풀이: 더 맵게 (0) | 2023.10.20 |
Step 4: 탐욕법(Greedy) 대표 문제 풀이: 큰 수 만들기 (0) | 2023.10.19 |
Step 2: 탐욕법(Greedy) 대표 문제 풀이: 체육복 (0) | 2023.10.19 |
Step 3: 정렬(Sort) 대표 문제 풀이: 가장 큰 수 (0) | 2023.10.19 |