[알고리즘 설명][Python] set, dict로 그래프 구현 및 그래프 탐색하기

이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.

혹시나 모르는 부분이 있으면 댓글로 질문해주세요.

 

한 줄 요약 : 만약 노드 번호가 매우 큰데 노드 개수가 적은 희소 그래프(sparse graph)이라면 dict로 그래프 선언하고, set으로 방문 체크 여부를 확인합니다.

 

우선 해당 그래프를 Python 소스 코드로 구현합니다.

N = 4

# 무방향 그래프이므로 양방향 edge 추가
def two_way_edges(u:int, v:int) -> None :
    graph[u].append(v)
    graph[v].append(u)
    return

graph:list = [[] for _ in range(N + 1)]

edges:str = """
1 2
1 3
2 4
3 4
"""

# 1. strip()으로 앞뒤의 불필요한 줄바꿈(\n)을 제거합니다.
# 2. splitlines()로 줄 단위로 잘라 리스트를 만듭니다.
for line in edges.strip().splitlines() :
    if not line.strip() :  # 혹시 모를 빈 줄 방지
        continue
        
    # 공백을 기준으로 나누어 정수형(int)으로 변환 후 언팩킹
    u, v = map(int, line.split())
    two_way_edges(u, v)

이렇게 해서 인접 리스트로 초간단하게 그래프 선언했습니다.

그리고 다음과 같은 소스 코드로 방문 체크를 할 수 있습니다.

visited:list = [False for _ in range(N + 1)]
visited[0] = True

이렇게 해서 방문 여부를 체크할 수 있습니다.

 

문제는 이런 그래프면 어떻게 구현해야 할까요?

노드의 번호가 무려 최대 2^64-1까지 나옵니다.

이것을 기존의 소스 코드대로 하면 어떻게 될까요?

N = (1 << 64) - 1

graph:list = [[] for _ in range(N + 1)]

visited:list = [False for _ in range(N + 1)]

이 경우는 visited의 크기는 128EiB, graph의 크기는 1ZiB입니다.

총 1.125ZiB가 나오는데 제타는 10^21이고 ZiB는 2^70 바이트입니다.

이것은 하드디스크 용량이 약 1TiB인 개인용 컴퓨터가 무려 악 193억대가 필요한 정신 나간 용량입니다.

 

이렇게 "노드 번호가 큰데 노드 개수가 희귀한 그래프"를 희소 그래프(sparse graph)라고 부릅니다.

이 그래프는 원래 희소 배열(sparse table) + 이분 점프(binary lifting)을 함께 사용해서 구현해야 하나 초보자에게 그건 정말 매우 어려운 알고리즘이거든요.

 

그래서 희소 그래프는 Python에서 dict로 그래프 선언하고, set으로 방문 여부를 체크할 수 있습니다.

우리는 복잡한 이론을 잊어버리고 실무에서 쉽게 구현하자고요!ㅎㅎ

graph:dict = dict()

visited:set = set()

이걸 활용해서 다음과 같이 소스 코드를 구현할 수 있습니다.

# 양방향 간선 추가 함수 (딕셔너리 리스트 버전)
def two_way_edges(u:int, v:int) -> None :
    # 딕셔너리에 노드 키가 아직 없다면 빈 리스트[]를 먼저 생성해 줍니다.
    if u not in graph:
        graph[u] = []
    if v not in graph:
        graph[v] = []
    # 그래프 정보(edge)를 저장합니다.
    graph[u].append(v)
    graph[v].append(u)
    return

# 그래프(사전)
graph:dict = dict()
# 방문 여부 확인(집합)
visited:set = set()

edges:str = """
17179869184 17592186044416
17179869184 18014398509481984
17592186044416 18446744073709551615
18014398509481984 18446744073709551615
"""

for line in edges.strip().splitlines():
    if not line.strip():  # 혹시 모를 빈 줄 방지
        continue
        
    # 공백을 기준으로 나누어 정수형(int)으로 변환 후 언팩킹
    u, v = map(int, line.split())
    two_way_edges(u, v)
    
for key, value in graph.items() :
    print(f"key: {key} -> values: {value}")

[결과]

key: 17179869184 -> values: [17592186044416, 18014398509481984]
key: 17592186044416 -> values: [17179869184, 18446744073709551615]
key: 18014398509481984 -> values: [17179869184, 18446744073709551615]
key: 18446744073709551615 -> values: [17592186044416, 18014398509481984]

이렇게 해서 2^34, 2^44, 2^54, 2^64-1 노드들이 담긴 희소 그래프를 구현하는데 성공했습니다!

 

그러면 아주 간단한 그래프 탐색을 해야겠죠?

현재 2^44는 이미 방문 처리했다고 가정합니다.

그러면 다음 코드 한 줄을 추가해주세요.

visited.add(17592186044416)

이렇게 하면 2^44 노드는 방문 처리된 것입니다.

 

여기서는 정말 간단하게 해서 "2^34 노드들 주변에 아직 방문하지 않는 노드들을 탐색하자!"입니다.

2^34 노드 주변에는 2^44 노드와 2^64-1 노드가 존재합니다.

# 양방향 간선 추가 함수 (딕셔너리 리스트 버전)
def two_way_edges(u:int, v:int) -> None :
    # 딕셔너리에 노드 키가 아직 없다면 빈 리스트[]를 먼저 생성해 줍니다.
    if u not in graph:
        graph[u] = []
    if v not in graph:
        graph[v] = []
        
    graph[u].append(v)
    graph[v].append(u)
    return

# 그래프(사전)
graph:dict = dict()
# 방문 여부 확인(집합)
visited:set = set()

edges:str = """
17179869184 17592186044416
17179869184 18014398509481984
17592186044416 18446744073709551615
18014398509481984 18446744073709551615
"""

for line in edges.strip().splitlines():
    if not line.strip():  # 혹시 모를 빈 줄 방지
        continue
        
    # 공백을 기준으로 나누어 정수형(int)으로 변환 후 언팩킹
    u, v = map(int, line.split())
    two_way_edges(u, v)

# --- [여기서부터 시뮬레이션 시작] ---

# 1. 2^44 노드(17592186044416)를 미리 방문 처리합니다.
visited.add(17592186044416)
print(f"[초기 설정] 17592186044416 (2^44) 노드 사전 방문 처리 완료! | 현재 visited: {visited}")
print("-" * 75)

# 가독성을 위해 거대한 노드 번호를 별칭(2^k)으로 매핑해 주는 딕셔너리 (출력용)
NODE_NAMES = {
    17179869184: "2^34",
    17592186044416: "2^44",
    18014398509481984: "2^54",
    18446744073709551615: "2^64-1"
}

# 2. 2^34 노드 주변의 인접 노드들을 탐색합니다.
curr_node: int = 17179869184  # 2^34 노드
curr_name: str = NODE_NAMES[curr_node]
visited.add(curr_node) # 처음 노드를 방문했으니 방문 처리해줍니다.

print(f"[탐색 진행] {curr_node} ({curr_name}) 노드 주변의 연결된 노드들을 확인합니다...")

for next_node in graph[curr_node]:
    next_name = NODE_NAMES.get(next_node, "Unknown")
    
    # set에 이미 존재하는지 O(1) 해시 검색으로 즉시 확인!
    if next_node in visited:
        print(f"  └─ {next_node} ({next_name}) 노드는 이미 탐색(방문)했으니 넘어갈게요!")
    else:
        visited.add(next_node)
        print(f"  └─ {next_node} ({next_name}) 노드 탐색 완료! 이제 방문 처리할게요!")

print("-" * 75)
print(f"[최종 상태] 탐색 종료 후 visited 집합: {visited}")

[결과]

[초기 설정] 17592186044416 (2^44) 노드 사전 방문 처리 완료! | 현재 visited: {17592186044416}
---------------------------------------------------------------------------
[탐색 진행] 17179869184 (2^34) 노드 주변의 연결된 노드들을 확인합니다...
  └─ 17592186044416 (2^44) 노드는 이미 탐색(방문)했으니 넘어갈게요!
  └─ 18014398509481984 (2^54) 노드 탐색 완료! 이제 방문 처리할게요!
---------------------------------------------------------------------------
[최종 상태] 탐색 종료 후 visited 집합: {17592186044416, 17179869184, 18014398509481984}

이렇게 해서 2^34 노드, 2^44 노드, 2^64-1 노드들을 모두 방문했습니다.

 

그 외에도 "010-1234-5678"같은 전화번호를 "1012345678"형식으로 저장해서 전화번호를 노드로 취급하는 희소 그래프도 가능합니다.

이렇게 해서 오늘 희소 그래프(sparse graph)를 초간단하게 알아봤습니다.

실제로 Spring Boot로 JSON 객체들을 가져올 때 이 자료 구조가 엄청 자주 쓰입니다.

CS 분야에서 전공 서적만 보면 희소 그래프(sparse graph)가 뭔가 엄청 어렵고 무섭게 느껴지지만 개발하다 보면 JSON 객체에서 key끼리 연결할 때 자연스럽게 이 자료 구조를 자기도 모르게 쓰고 있어요!

그러니 겁먹지 마세요! 희소 그래프 별거 아닙니다!