JUNGLE 240328 (W02)

in Study #Jungle

KRAFTON JUNGLE Week 02

1. Keywords

그래프 (Graph)

노드 (Node)
  • 노드는 그래프의 구성 요소 중 하나로, 객체를 나타냄
  • 다른 용어로는 정점(Vertex)이라고 함
  • 노드는 일반적으로 데이터를 저장하는데 사용
  • Ex. 소셜 네트워크에서 각 사용자는 하나의 노드로 나타낼 수 있음
엣지 (Edge)
  • 엣지는 노드들 간의 관계를 나타냄
  • 두 개의 노드 사이의 관계를 표현
  • 엣지는 일반적으로 노드 간의 관계를 나타내는 추가 정보(가중치, 비용 등)를 가질 수 있음

그래프의 종류

무방향 그래프 (Undirected Graph)
  • 엣지에 방향이 없는 그래프
  • 노드 간의 연결 관계가 양방향으로 이루어짐
  • Ex. 친구 관계를 나타내는 소셜 네트워크 그래프
방향 그래프 (Directed Graph)
  • 엣지에 방향이 있는 그래프
  • 노드 간의 연결 관계가 단방향으로 정의됨
  • Ex. 웹페이지 간의 하이퍼링크를 나타내는 웹 그래프
가중치 그래프 (Weighted Graph)
  • 엣지에 가중치(Weight)가 할당된 그래프
  • 각 엣지가 어떤 값을 가지고 있는 경우 (거리, 비용, 용량 등)
  • Ex. 도로 네트워크를 나타내는 그래프에서 각 도로가 거리를 나타내는 경우

그래프의 표현 방식

    A
   / \
  B - C
 /   /
D - E
인접 행렬 (Adjacency Matrix)
    A  B  C  D  E
A   0  1  1  0  0
B   1  0  1  1  0
C   1  1  0  1  1
D   0  1  1  0  1
E   0  0  1  1  0
  • 2차원 배열로 그래프를 표현
  • 행과 열은 그래프의 정점을 나타내며, 해당 정점에서 다른 정점으로의 엣지 여부를 나타내는 값으로 채워짐
  • 만약 두 정점이 연결되어 있다면 해당 셀에 1 또는 가중치 값이 들어가고, 연결되어 있지 않다면 0 또는 무한대의 값을 가짐
  • 인접 행렬은 무방향 그래프의 경우 대각선을 기준으로 대칭이 되며, 방향 그래프의 경우 대칭이 아닐 수 있음
  • ✔ 장점: 두 정점 간의 연결 여부를 상수 시간 안에 확인 가능, 행렬의 크기가 작을 때 효율적
  • ✔ 단점: 밀집된 그래프의 경우 메모리 공간을 많이 차지
인접 리스트 (Adjacency List)
A: [B, C]
B: [A, C, D]
C: [A, B, D, E]
D: [B, C, E]
E: [C, D]
  • 각 정점마다 해당 정점과 연결된 다른 정점들의 리스트를 저장
  • 각 정점마다 연결된 정점들의 목록을 효율적으로 관리할 수 있음
  • 무방향 그래프의 경우 각 엣지가 두 번씩 나타나므로, 두 정점의 인접 리스트에 각각 추가
  • ✔ 장점: 희소 그래프에 효율적이고 메모리 공간을 더 효율적으로 사용 가능
  • ✔ 단점: 각 정점의 인접 리스트를 순회하면서 연결된 정점을 확인해야 하므로, 인접 행렬에 비해 더 많은 시간이 소요

BFS & DFS

자세한 내용은 여기로.. Click!!

DFS (깊이 우선 탐색)
  • 한 정점에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법
  • 트리의 깊은 곳을 먼저 탐색하고 나중에 넓게 탐색
  • 스택(Stack) 또는 재귀(Recursion)를 사용하여 구현
BFS (너비 우선 탐색)
  • 시작 정점에서부터 인접한 정점을 먼저 모두 탐색하는 방법
  • 트리의 같은 레벨을 우선적으로 탐색하고, 그 다음 레벨로 이동
  • 큐(Queue)를 사용하여 구현

위상 정렬 (Topological Sorting)

  • 방향 그래프에서 정점들을 일렬로 나열하는 과정
  • 그래프 상에서 방향을 따르면서 어떤 정점이 다른 정점보다 먼저 나와야 하는지 결정
  • 사이클이 없는 방향 그래프에서만 가능 (순환 구조를 가지면 위상 정렬 X)
  • 한 정점에서 다른 정점으로의 방향이 존재한다면, 해당 정점은 이전 정점보다 나중에 위치해야 함
  • 대표적으로 DFS & BFS 알고리즘을 활용해 구현 가능
위상 정렬을 하는 이유
  1. 의존 관계 파악: 정점들 간의 의존 관계 파악
  2. 작업 순서 결정: 작업이 서로 의존하거나 선후 관계가 있는 경우, 위상 정렬을 통해 작업을 순서대로 수행 가능
  3. 순환 의존성 탐지: 위상 정렬을 수행하는 과정에서 사이클이 발견되면, 이는 의존성 관계에 순환성이 있음을 의미
  4. 이벤트 처리: 이벤트 처리 시스템에서 이벤트의 처리 순서를 결정할 때 사용 가능
DFS로 구현한 위상 정렬
def topological_sort(graph):
    def dfs(node):                            # 한 정점에서 시작하여 그래프를 깊이 우선 탐색
        visited.add(node)                     # 방문한 정점들 기록
        for neighbor in graph.get(node, []):
            if neighbor not in visited: 
                dfs(neighbor)                 # dfs 함수 재귀 호출
        result.append(node)

    visited = set()                           # 방문한 정점들의 집합
    result = []                               # 방문한 정점들의 순서 저장

    for node in graph.keys():                 # 주어진 그래프의 모든 정점을 순회
        if node not in visited:               # 방문하지 않은 정점을 발견하면 DFS 시작
            dfs(node)

    return result[::-1]                       # 위상 정렬된 순서로 정점들이 담겨있음 (역순으로 반환)
  • DFS를 사용하여 그래프 순회
  • 재귀 호출이 모두 완료되면 결과 리스트에는 위상 정렬된 순서로 저장됨
BFS로 구현한 위상 정렬

영상 참고

def topological_sort_bfs(graph):
    # 각 정점의 진입 차수를 저장하는 딕셔너리
    in_degree = {node: 0 for node in graph.keys()}
    for neighbors in graph.values():    # 각 정점에 대한 인접한 정점들을 순회하고, 각 정점의 진입 차수 증가
        for neighbor in neighbors:
            in_degree[neighbor] += 1

    # 위상 정렬 결과를 저장할 리스트
    result = []

    # 진입 차수가 0인 정점들을 큐에 추가
    queue = deque([node for node, degree in in_degree.items() if degree == 0])

    # BFS를 사용하여 진입 차수가 0인 정점들부터 순차적으로 처리
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph.get(node, []):    # 해당 정점과 연결된 다음 정점들을 순회
            in_degree[neighbor] -= 1            # 현재 정점과 연결된 정점의 진입 차수를 1 감소
            if in_degree[neighbor] == 0:        # 해당 정점으로 들어오는 모든 엣지를 방문한 경우,  
                queue.append(neighbor)          # 해당 정점을 큐에 추가

    # 사이클이 있는 경우 처리
    if len(result) != len(graph):
        raise ValueError("그래프에는 사이클이 존재합니다.")

    return result
  • 각 정점의 진입 차수를 계산하고 진입 차수가 0인 모든 정점을 큐에 추가
  • 큐를 사용하여 진입 차수가 0인 정점들부터 순차적으로 처리
  • 정점을 방문할 때마다 해당 정점과 연결된 다음 정점들의 진입 차수를 감소시킴
  • BFS를 마치고 나면 큐에는 위상 정렬된 순서로 저장됨