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

김경민·2023년 1월 10일
0
post-thumbnail

BFS & DFS

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


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

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

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시간 이상이 지났고, 제출 후 정확성은 맞았으나 시간초과가 나서 일단 휴전 협정 후 내일 다시 싸울 예정이당.
    부끄러운 나의 코드와 생각은 해결 후 내일 업로드 예정
profile
안녕하세요

0개의 댓글