[정글 베이직 22] 그래프 기본 - 인접 리스트 표현 완전 정리

그래프 기초

그래프 기본 - 인접 리스트 표현 완전 정리

그래프 문제를 풀기 위해서는 먼저 그래프를 코드로 표현할 수 있어야 합니다. 그중 가장 자주 쓰는 방식이 바로 인접 리스트입니다.

그래프란?

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 트리와 달리 일반적인 연결 관계를 자유롭게 표현할 수 있습니다.

정점: 연결의 대상이 되는 점

간선: 정점과 정점을 이어주는 선

인접 리스트란?

인접 리스트는 각 정점마다 연결된 다른 정점들의 목록을 저장하는 방식입니다.

예시 형태

{정점: [연결된 정점들]}

왜 많이 쓸까?

간선 수가 많지 않은 그래프에서 메모리 효율이 좋고, BFS/DFS 구현과도 잘 어울립니다.

예제 그래프

0 ─── 1
│       │
└ 2 ── 3

간선이 [(0,1), (0,2), (1,2), (2,3)] 이라고 하면, 무방향 그래프의 인접 리스트는 다음과 같이 표현됩니다.

정점	연결된 정점들
0	[1, 2]
1	[0, 2]
2	[0, 1, 3]
3	[2]

방향 그래프 vs 무방향 그래프

무방향 그래프

u와 v가 연결되면 u → v 뿐 아니라 v → u도 함께 저장합니다.

방향 그래프

u → v만 저장하고, 반대 방향은 자동으로 추가하지 않습니다.

풀이 핵심

먼저 모든 정점에 대해 빈 리스트를 만들고, 간선 목록을 돌면서 하나씩 연결 정보를 추가하면 됩니다. 무방향 그래프라면 반대 방향도 함께 추가하는 것이 포인트입니다.

정답 코드

def create_graph(vertices, edges, directed=False):
    """
    그래프 생성 (인접 리스트)
    """
    graph = {i: [] for i in range(vertices)}

    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)

    return graph

# 테스트 케이스
if __name__ == "__main__":
    vertices = 4
    edges = [(0, 1), (0, 2), (1, 2), (2, 3)]

    print("=== 무방향 그래프 ===")
    graph = create_graph(vertices, edges, directed=False)
    for vertex, neighbors in graph.items():
        print(f"{vertex} → {neighbors}")
    print()

    print("=== 방향 그래프 ===")
    graph_directed = create_graph(vertices, edges, directed=True)
    for vertex, neighbors in graph_directed.items():
        print(f"{vertex} → {neighbors}")

한 줄 요약

그래프 인접 리스트는 각 정점에 연결된 정점들을 리스트로 저장하는 방식이며, 무방향 그래프는 양방향으로 추가합니다.