🚶‍♂️Road to 코테(12) - 그래프

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬

[추가] 좌충우돌, 파이썬으로 자료구조 구현하기

[추가] 개발자 남노씨 알고리즘 특강.

그래프(Graph) 정리

그래프는 현실 세계의 복잡한 관계를 효과적으로 모델링할 수 있는 대표적인 자료구조입니다. 아래는 그래프의 정의, 종류, 활용, 그리고 코드로 표현하는 방법까지 한눈에 정리한 내용입니다.

그래프의 정의

그래프(Graph)는 객체(노드, 정점)와 이들 사이의 연결(간선)로 구성된 자료구조입니다.
즉, 정점(Vertex, Node)의 집합 V와 간선(Edge)의 집합 E로 이루어져 있습니다.
그래프는 비선형 자료구조로, 트리보다 더 다양한 연결 구조를 표현할 수 있습니다.

현실 세계의 객체와 그 연결 관계를 그래프 자료구조로 표현할 수 있습니다.
객체는 노드(정점), 연결 관계는 간선으로 정의할 수 있습니다.

예시:
노드(정점): A, B, C, D, E, F
간선: A-B, B-C, B-E, C-D, E-D, E-F

그래프의 활용 예시

그래프는 다양한 분야에서 활용됩니다:
교통망/지도: 도시(정점), 도로(간선)
컴퓨터 네트워크: 컴퓨터/라우터(정점), 연결(간선)
소셜 네트워크: 사용자(정점), 친구/팔로우(간선)
네비게이션, 추천 시스템 등
그래프 탐색 알고리즘(DFS, BFS 등)을 활용해 최단거리, 경로 탐색, 네트워크 분석 등 문제를 해결할 수 있습니다.

그래프 종류

1. 무방향 그래프(undirected graph) vs 방향 그래프(directed graph)

• 무방향 그래프(Undirected Graph)
  

  - 간선에 방향성이 없는 그래프입니다. 두 노드는 양방향으로 연결됩니다.
  - A→B로 갈 수 있으며, B→A로도 갈 수 있습니다. 서로 연결된 상태입니다.

  • 방향 그래프(Directed Graph)

간선에 방향성이 있음. A→B는 되지만, B→A는 이동 불가

• 간선에 방향성이 있는 그래프입니다. 간선이 A에서 B로 향하면, A에서 B로만 이동할 수 있습니다.
  - 그래프를 자세히 살펴보면 들어오는 간선과 나가는 간선으로 구분할 수 있습니다. 이때, 들어오는 간선을 indegree, 나가는 간선을 outdegree라고 합니다.
  - 예를 들어, 정점 B를 살펴보면 A와 C로부터 들어오는 indegree가 2개, E로 나가는 outdegree가 1개임을 알 수 있습니다.

2. 단순 vs 다중

• 단순
  
  - 자기 자신을 연결하는 간선(Self-loop)이 없는 그래프입니다
  - 두 정점 사이에 간선이 하나만 존재합니다.
  

3.가중치 그래프 vs 비가중치 그래프

4. 순환 그래프 vs 비순환 그래프

• 순환 그래프(Cyclic Graph)
  - 적어도 하나 이상의 사이클(출발한 정점으로 다시 돌아오는 경로)이 존재하는 그래프입니다.
  -비순환 그래프(Acyclic Graph)
  - 사이클이 존재하지 않는 그래프를 의미합니다.
  - 방대표적인 예로 트리, 방향 비순환 그래프(DAG, Directed Acyclic Graph)가 있습니다.

방향 비순환 그래프(DAG, Directed Acyclic Graph)란 말 그대로 방향성이 있는 그래프(Directed Graph) 중 사이클이 없는 그래프를 의미합니다. DAG는 위상 정렬(Topological Sorting)이 가능하며, 작업 스케줄링, 의존성 그래프, 컴파일러 최적화 등의 문제에서 자주 활용됩니다.

그래프의 용어

• 정점(Vertex, Node): 데이터를 저장하는 단위
• 간선(Edge): 두 정점을 연결하는 선
• 인접(Adjacency): 두 정점이 간선을 통해 연결된 상태
• 경로(Path): 두 정점을 잇는 간선의 순서
• 사이클(Cycle): 시작 정점으로 다시 돌아오는 경로
• 차수(Degree): 정점에 연결된 간선의 개수 (방향 그래프에서는 진입차수/진출차수로 구분)

그래프의 표현 방법 (코드 구현)

그래프를 코드로 표현하는 대표적인 방법은 세 가지입니다:

1. 인접 행렬 (Adjacency Matrix)
   2차원 배열로 노드 간 연결 관계를 표현
   연결되어 있으면 1(또는 가중치), 아니면 0

int[][] matrix = {
    {0, 1, 0, 0, 0, 0}, // A
    {1, 0, 1, 0, 1, 0}, // B
    {0, 1, 0, 1, 0, 0}, // C
    {0, 0, 1, 0, 1, 1}, // D
    {0, 1, 0, 1, 0, 1}, // E
    {0, 0, 0, 1, 1, 0}, // F
};

장점: 간선 존재 여부를 즉시 확인 가능
단점: 정점 수가 많고 간선이 적은 경우(희소 그래프) 메모리 낭비가 큼

2. 인접 리스트 (Adjacency List)
   각 정점이 연결된 정점 목록을 리스트(혹은 맵)로 저장
   희소 그래프에서 메모리 효율적
   

장점: 메모리 효율적, 노드 추가/삭제 용이
단점: 연결 여부 확인은 인접 행렬보다 느릴 수 있음

Map<String, List<String>> graph = new HashMap<>() {{
    put("A", List.of("B"));
    put("B", List.of("A"));
    put("C", List.of());
    put("D", List.of());
    put("E", List.of());
    put("F", List.of());
}};

3. 암시적 그래프 (Implicit Graph)
   노드와 간선을 명시적으로 저장하지 않고, 규칙이나 수식으로 연결 관계를 정의
   예: 2차원 배열에서 상하좌우 이동, 퍼즐 문제 등
   좌표 상에서 dfs/bfs하는 것. 0,1 판단하는 것.

인접 리스트 변환 방법

• case1) 간선 정보가 입력값으로 나올 때

문제에서 간선 정보(edges)가 주어질 때, 이를 인접 리스트(list)로 변환할 수 있습니다

edges = [[0, 1], [0, 3], [0, 6], [1, 3], [2, 3], [3, 7], [4, 5], [5, 6], [5, 7]]
n = 8 # 노드의 개수

인접 리스트 변환 코드

// 인접 리스트 초기화
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
    graph.add(i, new ArrayList<>()); // 각 노드에 대해 빈 리스트 추가
}

// 양방향 간선 추가
for (int[] edge : edges) {
    int a = edge[0];
    int b = edge[1];

    graph.get(a).add(b); // a -> b 연결
    graph.get(b).add(a); // b -> a 연결 (양방향)
}

일방향 그래프인 경우

만약 문제에서 일방향 그래프라고 명시되었다면, 다음과 같이 변환해야 합니다.

// 인접 리스트 초기화
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>()); // 각 노드에 대해 빈 리스트 추가
}

// 일방향 간선 추가
for (int[] edge : edges) {
    int a = edge[0];
    int b = edge[1];

    graph.get(a).add(b); // a -> b 연결
}

• case2) 인접 리스트(list)를 입력값을 줄 때
  일부 문제에서는 이미 인접 리스트(list) 형태로 입력이 제공되기도 합니다.

List<List<Integer>> graph = new ArrayList<>() {{
    add(List.of(1, 3, 6));
    add(List.of(0, 3));
    add(List.of(3));
    add(List.of(0, 1, 2, 7));
    add(List.of(5));
    add(List.of(4, 6, 7));
    add(List.of(0, 5));
    add(List.of(3, 5));
}};