[TIL 2/3] BFS & DFS, 문제와의 2시간 이상의 사투 (휴전)

BFS & DFS

• 대표적인 그래프 탐색 알고리즘
  • 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
  • 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

출처 : https://iq.opengenus.org/dfs-vs-bfs/

파이썬으로 그래프를 표현하는 방법

• 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있다.
  
  출처 : https://www.fun-coding.org

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

BFS

def bfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    return visited

DFS

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    return visited

• 회고
  BFS와 DFS의 구현은 친절한 파이썬 덕분에 어렵지 않지만 오늘 알고리즘 친구를 만나서 사투를 벌이고는 휴전 상태이다.
  게임맵 최단거리
  30분만 잡아보고 안되면 정답을 보고자 했지만 내 힘으로 풀고 싶어서 20분만 20분만 하다가 2시간 이상이 지났고, 제출 후 정확성은 맞았으나 시간초과가 나서 일단 휴전 협정 후 내일 다시 싸울 예정이당.
  부끄러운 나의 코드와 생각은 해결 후 내일 업로드 예정