99클럽 코테 스터디 2일차 TIL + BFS

❇️오늘의 학습 키워드 : BFS

 

BFS?

- BFS는 탐색 시작점에서 가까운 노드부터 차례로 탐색하는 알고리즘(넓이 우선 탐색)

- 큐(Queue) 자료구조를 사용하여 방문해야 할 노드를 저장하고, 가장 먼저 큐에 추가된 노드부터 탐색(FIFO)

BFS의 동작 원리

    (1) 시작 노드를 큐에 삽입 + 방문처리

    (2) 큐에서 노드를 꺼내고, 해당 노드에 인접한 노드들 확인 -> 방문하지 않은 인접 노드는 큐에 추가+방문처리

    (3) 1, 2를 큐가 빌 때까지 반복

BFS의 특징

- DFS가 경우의 수를 탐색하는데 유리하다면, BFS는 노드와 노드의 관계(최단 경로 등)를 탐색하는데 유리하다!

BFS 코드 예제

for i in range(1, n+1):
    q = deque([(i,0)])
    visited = [0] *(n + 1)
    visited[i] = 1
    while q:
        node, d = q.popleft()
        for child in dp[node]:
                if visited[child] == 0:
                    visited[child] = 1
                    dist[i][child] = d + 1 # 이전거리 +1
                    q.append((child, d+1))

깊이(거리)를 구하려면 이런 식으로 코드를 작성할 수 있다! 

❇️오늘의 회고

  - 2일차 문제는 1일차에 학습했던 플로이드-워셜 알고리즘을 사용해서도 풀 수 있는데, 아무래도 BFS보다 시간복잡도가 높다. ( 물론 노드의 수가 100밖에 되지 않아 사용해도 시간초과는 나지 않는다.)

  - BFS는 정말 중요한 알고리즘이므로 복습, 또 복습을 해야만한다... 처음 문제를 풀 때 부분부분만 기억나서 힘들었다^^;;

  - 내일 11시, 문제를 풀기 전에 위 개념을 한번 더 복습하고 내일 문제에 사용된 알고리즘에 대해서 더 깊이 공부할 것이다! 😋 화이팅!