[Algorithm - DFS/BFS] 그래프와 깊이/너비 우선 탐색 (Programmers - 여행경로)

1. 그래프

• 정점(vertex, node)과 간선(edge, link)
• 유향(directed)그래프와 무향(undirected)그래프
• 스택과 큐로 구현 가능

 

2. 깊이 우선 탐색 (DFS; Depth-First Serach)

• 한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
• 순서가 정해져있진 않으나 일반적으로 가장 좌측에서 아래로 깊이 우선 탐색 진행
• 무향 그래프 예시 (0 > 1 > 3 > 7 > 4 > 5 > 2 >6)

• 스택을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아감

 

3. 너비 우선 탐색(BFS; Breadth-First Search)

• 한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로(방문한 순서에 따라) 또 다시 너비 우선 탐색을 행함
• 일반적으로 좌측에서 오른쪽으로 넓이 우선 탐색 진행
• 무향 그래프 예시 (0 > 1 > 3 > 7 > 4 > 5 > 2 > 6)

• 큐를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행함

 

4. Programmers - 여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

• 문제 요약
  • 재귀적인 성질을 가진 "한 붓 그리기"문제 -> 재귀적인 성질을 가진 "그래프의 깊이 우선 탐색"을 응용해야 함

from collections import defaultdict

def solution(tickets):
    answer = []
    tickets_dic = defaultdict(list)
    for depart, arrive in tickets:
        tickets_dic[depart].append(arrive)
    
    for key in tickets_dic:
        tickets_dic[key].sort(reverse=True)

    qlist = ['ICN']
    while qlist:
        depart = qlist[-1]

        # 순방향 경로 저장
        if tickets_dic[depart]:
            qlist.append(tickets_dic[depart].pop())
        else:
            # 순방향 길이 끊겼을 때 역방향 경로 저장
            answer.append(qlist.pop())
            
    return list(reversed(answer))