[코딩테스트 합격자 되기 파이썬] - 2주차 스터디 - BFS

1. BFS(너비 우선 탐색) 알고리즘의 작동 원리를 설명하고, 어떤 자료구조를 사용하는지, 그리고 그 이유는 무엇인지 설명해주세요.

BFS(너비 우선 탐색)는 그래프나 트리에서 시작 정점에서부터 인접한 노드를 먼저 방문하는 알고리즘입니다. BFS의 핵심 아이디어는 시작 정점으로부터 거리가 가까운 노드들을 먼저 처리하고, 그 다음 거리에 있는 노드들을 차례대로 탐색하는 것입니다.

먼저 BFS의 작동 원리를 정리하면 다음과 같습니다.

1. 시작 정점 선택: 탐색의 출발점이 되는 정점을 선택합니다.
2. 큐(Queue) 사용: BFS에서는 FIFO(First-In, First-Out) 원칙을 따르는 큐를 사용합니다. 즉, 먼저 방문한 정점부터 처리하게 되어, 각 단계별(레벨별)로 노드를 확장합니다.
3. 인접 노드 방문: 현재 정점과 연결된 모든 인접 노드를 방문하고, 아직 방문하지 않은 노드를 큐에 추가합니다.
4. 반복: 큐가 빌 때까지 위 과정을 반복하여 모든 노드를 방문합니다.

자료구조로 큐를 사용하는 이유는 다음과 같습니다.

• FIFO 특성: 먼저 들어간 노드가 먼저 처리되므로, 각 레벨의 노드가 순서대로 방문되어 BFS가 레벨 순회 방식을 구현할 수 있습니다.
• 최단 경로 보장: 무가중치 그래프에서 시작 정점으로부터 가장 짧은 경로를 탐색할 때 효과적입니다.
• 효율적인 방문 처리: 방문한 노드를 추적하기 위해 집합(set) 또는 방문 배열을 사용하여 중복 방문을 방지할 수 있습니다.

아래는 파이썬 코드 예제와 함께 그래프 시각화를 통해 BFS를 구현한 코드입니다.

import matplotlib.pyplot as plt
import networkx as nx
from collections import deque

# 그래프 시각화를 위한 그래프 생성
G = nx.Graph()
edges = [
    ('A', 'B'),
    ('A', 'C'),
    ('B', 'D'),
    ('B', 'E'),
    ('C', 'F'),
    ('C', 'G')
]
G.add_edges_from(edges)

# 위치 배치 및 그래프 시각화
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=800, font_size=12)
plt.title("BFS 탐색 대상 그래프")
plt.show()

# BFS 알고리즘 구현 함수
def bfs(graph, start):
    visited = set()         # 방문한 노드를 추적하기 위한 집합
    queue = deque([start])  # 시작 정점을 큐에 추가 (FIFO 성질 활용)
    order = []              # 방문 순서를 기록할 리스트
    
    while queue:
        node = queue.popleft()  # 큐의 가장 앞에 있는 노드를 추출
        if node not in visited:  # 아직 방문하지 않은 노드라면
            visited.add(node)  # 노드를 방문 처리
            order.append(node) # 방문 순서 기록
            # 현재 노드의 인접 노드들을 큐에 추가, 중복 방문 방지
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
    return order

# 인접 리스트 형태의 간단한 그래프 정의
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C'],
    'G': ['C']
}

# BFS 탐색 실행 및 결과 출력
bfs_order = bfs(graph, 'A')
print("BFS 탐색 순서 (시작 정점 A부터):", bfs_order)

이 코드는 다음과 같은 과정을 거칩니다.

• 그래프 시각화: networkx 라이브러리를 사용해 그래프를 생성하고, matplotlib로 시각화하여 BFS 탐색 대상의 전체 구조를 쉽게 파악할 수 있게 합니다.
• BFS 함수:
  • deque를 이용해 큐를 구현합니다.
  • visited 집합을 활용하여 이미 방문한 노드를 기록하고, 중복 처리를 방지합니다.
  • 큐에서 하나씩 노드를 꺼내고, 인접 노드를 방문하며 순서를 기록합니다.
• 탐색 결과 출력: BFS의 탐색 순서를 출력하여, 시작 정점 A부터 방문된 노드의 순서를 확인할 수 있습니다.

이와 같이 BFS는 레벨 순서대로 정점을 방문하며, 큐 자료구조를 통해 효과적으로 탐색을 수행할 수 있습니다. 이 설명과 코드는 BFS의 작동 원리와 그 구현 방식을 충분히 상세히 다루고 있어, 알고리즘을 이해하는 데 큰 도움이 될 것입니다.

2. BFS와 DFS(깊이 우선 탐색)의 차이점은 무엇이며, 각각 어떤 종류의 문제에 더 적합한지 예시를 들어 설명해주세요.

BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 둘 다 그래프 탐색 알고리즘이지만, 탐색 방식과 사용 목적에 차이가 있습니다.

1. 탐색 방식의 차이

• BFS (Breadth First Search):
  • 탐색 순서: 시작 정점에서부터 인접한 모든 정점을 먼저 방문한 후, 그 다음 단계(레벨)의 정점들을 차례대로 방문합니다.
  • 자료구조: FIFO(First-In, First-Out) 방식의 큐(Queue)를 사용합니다.
  • 특징:
    • 레벨 순서대로 탐색하기 때문에, 무가중치 그래프에서 최단 경로를 찾는 데 유리합니다.
    • 탐색 경로가 넓게 확장되므로, 메모리 사용량이 많을 수 있습니다(특히 레벨이 높을 경우).
• DFS (Depth First Search):
  • 탐색 순서: 시작 정점에서 한 방향으로 끝까지 깊이 내려간 후, 더 이상 진행할 수 없게 되면 이전 정점으로 돌아가 다른 경로를 탐색합니다.
  • 자료구조: LIFO(Last-In, First-Out) 특성을 가지는 스택(Stack) 또는 재귀 함수를 사용합니다.
  • 특징:
    • 경로를 따라 깊게 탐색하기 때문에, 특정 경로의 존재 여부를 빠르게 판단할 수 있습니다.
    • 전체 경로를 깊게 탐색하는 특성상, 경로 길이에 따라 스택 메모리 사용량이 증가할 수 있습니다.

2. 문제 유형에 따른 적합성

BFS가 더 적합한 문제 예시

• 최단 경로 탐색 (Shortest Path in Unweighted Graphs):
  BFS는 시작점에서부터의 거리를 레벨별로 탐색하기 때문에, 간선의 가중치가 없거나 동일한 경우 최단 경로를 쉽게 구할 수 있습니다.
  예시: 미로 찾기에서 출발점부터 도착점까지 최소 이동 횟수를 구하는 문제.
• 레벨 순회 및 최단 거리 계산:
  네트워크나 소셜 미디어 연결 요소 분석 등에서, 특정 노드로부터의 거리에 따른 분석이 필요할 때 유리합니다.

DFS가 더 적합한 문제 예시

• 경로의 존재 여부 탐색:
  DFS는 특정 경로를 깊게 따라 탐색하기 때문에, 두 노드 간의 경로가 존재하는지 빠르게 판별할 수 있습니다.
  예시: 사이클 찾기, 강한 연결 요소(scc) 탐색 등.
• 백트래킹(Backtracking)을 이용한 문제:
  미로 탐색, 퍼즐 문제, 조합 및 순열 문제 등에서 한 경로를 선택해 끝까지 탐색한 후, 조건에 맞지 않으면 이전 단계로 돌아가 다른 경로를 시도할 때 DFS가 많이 활용됩니다.
• 탑색 정렬(Topological Sort):
  방향성이 있는 그래프에서 순서를 결정할 때, DFS를 이용해 정렬을 수행하는 방식(DFS를 기반으로 한 위상 정렬)이 있습니다.

3. 간단한 파이썬 코드 예제

아래는 BFS와 DFS를 각각 구현한 파이썬 코드 예제로, 두 알고리즘의 차이점을 명확하게 보여줍니다.

BFS 예제 (최단 경로 탐색 용도)

from collections import deque

def bfs_shortest_path(graph, start, goal):
    # 큐에 (현재 정점, 경로)를 저장
    queue = deque([(start, [start])])
    visited = set()
    
    while queue:
        (vertex, path) = queue.popleft()
        if vertex in visited:
            continue
        visited.add(vertex)
        
        # 목표 정점에 도달했다면 경로 반환
        if vertex == goal:
            return path
        
        # 현재 정점의 인접 정점들을 탐색
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append((neighbor, path + [neighbor]))
    return None

# 예제 그래프 (인접 리스트)
graph_example = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B', 'H'],
    'F': ['C'],
    'G': ['C'],
    'H': ['E']
}

print("BFS 최단 경로 (A -> H):", bfs_shortest_path(graph_example, 'A', 'H'))

DFS 예제 (경로 존재 여부 및 깊이 탐색 용도)

def dfs(graph, start, goal, path=None, visited=None):
    if path is None:
        path = [start]
    if visited is None:
        visited = set()
    
    visited.add(start)
    
    # 목표 정점에 도달하면 경로 반환
    if start == goal:
        return path
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            result = dfs(graph, neighbor, goal, path + [neighbor], visited)
            if result is not None:
                return result
    return None

print("DFS 경로 탐색 (A -> H):", dfs(graph_example, 'A', 'H'))

4. 결론

• BFS와 DFS의 주요 차이점:
  BFS는 레벨 순서대로, 즉 가까운 노드부터 탐색하여 최단 경로를 보장하는 반면, DFS는 한 방향으로 깊게 탐색하는 알고리즘입니다.
• 문제에 따른 적합성:
  • 최단 경로, 레벨 순회 등에는 BFS가 더 적합합니다.
  • 경로의 존재 여부 판별, 백트래킹 문제, 위상 정렬 등에는 DFS가 유리합니다.

문제의 특성에 맞게 알고리즘을 선택하는 것이 중요한데, 예를 들어 무가중치 그래프에서 최단 경로를 구할 때는 BFS를, 특정 조건에 따른 모든 가능 경로를 탐색해야 할 때는 DFS를 선택하는 것이 일반적입니다.

 

3. BFS 알고리즘의 시간 복잡도는 O(V + E)인데, 그래프의 형태(예: 밀집 그래프 vs 희소 그래프)가 실제 수행 시간에 어떤 영향을 미칠 수 있을지 설명해주세요.

 

BFS 알고리즘의 시간 복잡도가 O(V + E)라는 것은, 알고리즘이 그래프의 모든 정점(V)과 모든 간선(E)을 한 번씩 처리한다는 의미입니다. 그러나 그래프의 형태에 따라 실제 수행 시간은 달라질 수 있습니다. 아래에서 밀집 그래프와 희소 그래프의 특성과, 이들이 BFS 수행 시간에 미치는 영향을 자세히 설명하겠습니다.

1. 그래프의 종류: 밀집 그래프 vs 희소 그래프

• 밀집 그래프 (Dense Graph):
  밀집 그래프는 정점 간 연결된 간선 수가 많다는 특징을 가집니다. 일반적으로 정점의 수가 V일 때, 간선의 수 E는 최악의 경우 O(V²)에 가까워집니다.
  • 예를 들어, V = 1000인 밀집 무방향 그래프에서 최대 간선 수는 약 500,000개가 될 수 있습니다.
• 희소 그래프 (Sparse Graph):
  희소 그래프는 정점이 많더라도 간선의 수가 상대적으로 적은 그래프입니다. 일반적으로 간선의 수가 O(V) 정도인 경우가 많습니다.
  • 예를 들어, V = 1000인 희소 그래프에서는 간선 수가 몇 천개 정도일 수 있습니다.

---

2. BFS 실행 시간에 미치는 영향

BFS의 시간 복잡도는 O(V + E)이므로, 실제 수행 시간은 V(정점 수)와 E(간선 수)에 따라 결정됩니다.

• 밀집 그래프의 경우:
  • 간선 수가 매우 많음:
    밀집 그래프에서는 E의 값이 매우 커지기 때문에, BFS가 간선들을 처리하는 데 드는 시간이 전체 수행 시간의 대부분을 차지하게 됩니다.
  • 실제 시간:
    예를 들어, 밀집 그래프의 경우 간선 수가 O(V²)라면, BFS의 시간 복잡도는 O(V + V²)에서 사실상 O(V²)로 표현할 수 있습니다.
    -> 결과적으로 정점 수가 커지면 수행 시간의 증가 폭이 기하급수적으로 커질 수 있습니다.
• 희소 그래프의 경우:
  • 간선 수가 상대적으로 적음:
    희소 그래프에서는 간선의 수가 O(V)에 가깝기 때문에, 전체 BFS 수행 시간은 O(V + V) = O(V)로 보다 효율적으로 동작할 수 있습니다.
  • 실제 시간:
    정점과 간선의 수가 적어, 많은 경우 BFS가 빠르게 실행됩니다. 특히, 정점 수가 많더라도 간선 수가 많지 않기 때문에, 처리해야 할 요소의 총 개수가 적어집니다.

---

3. 추가 고려 사항

• 상수 계수:
  알고리즘의 시간 복잡도 표현은 대수적 성장률을 나타내지만, 실제 구현에서는 자료구조 선택(예: 큐 구현에 사용하는 deque), 캐시 효율성, 메모리 접근 패턴 등 상수 계수가 실제 실행 시간에 영향을 줄 수 있습니다.
  • 밀집 그래프의 경우, 많은 간선을 처리해야 하므로 상수 계수의 영향이 더 뚜렷할 수 있습니다.
  • 희소 그래프에서는 이러한 영향이 상대적으로 미미할 수 있습니다.
• 메모리 사용:
  밀집 그래프에서는 많은 간선을 저장해야 하므로 메모리 사용량이 증가하며, 메모리 접근 비용이 BFS 수행 시간에 추가적인 영향을 줄 수 있습니다.
  반면, 희소 그래프는 메모리 요구량이 적어 이러한 문제가 덜 발생합니다.

---

4. 결론

BFS 알고리즘의 이론적 시간 복잡도는 O(V + E)로 정의되어 있으며, 이론적으로는 모든 그래프에 동일하게 적용됩니다. 하지만 실제 수행 시간은 그래프의 형태에 따라 크게 달라질 수 있습니다.

• 밀집 그래프에서는 간선의 수가 매우 많기 때문에 처리 시간의 대부분을 간선 탐색에 할애하게 되어, 성능이 저하될 가능성이 높습니다.
• 희소 그래프에서는 간선의 수가 적기 때문에, BFS가 빠르게 동작할 수 있으며, 전체 수행 시간도 비교적 짧습니다.

따라서, 문제에서 다루는 그래프의 특성을 고려하여 알고리즘 선택이나 최적화 방법을 결정하는 것이 중요합니다.

 

4. 문제풀이

1. 게임 맵 최단거리

https://studycord.tistory.com/103

[python] 프로그래머스 - 게임 맵 최단거리

 

2. 경주로 건설

돌아오는 주에 추가적으로 풀어보도록 하겠습니다.

시뮬레이션 문제만 풀다보니 미뤄뒀던 것 같습니다.

 

5. 회고

- 오늘 삼성 코딩테스트를 보고 왔습니다. 꾸준히 뭔가를 한다는 것이 정말 필요한 것임을 느끼게 되었습니다. 긴장하고, 초조해하다보니 알고 있다고 생각한 부분도 알 수 없고, 잔잔한 실수들도 많이 나왔습니다.

- 시간 복잡도를 계산하면서 푸는 연습을 진행해야겠습니다. (실제 시험에서 매우 중요한 것을 느꼈습니다.....)

- 메모리관리, 시간 설정하고 문제풀이, 일정 기간 후 다시 문제 풀어보기 등 다양한 방법을 활용하면서 꾸준히 나아가겠습니다.