🔄그래프 표현을 위한 인접 리스트 입력, 변환

관련글 : 

인접 리스트 배열 초기화

https://waydd.tistory.com/153

 

 

1. 그래프 간선 입력 받기

 

간선 리스트 (간선만 모음) 를 입력 받는 것

→ 정렬 및 MST 알고리즘에 사용

→ 그래프 생성시 사용

 

- 그래프 

• 내장 함수 input 사용 ❌ → 빠른 입력
• 정점 튜플 리스트로 간선 목록 저장
• 가중치 유무 범용

# 공통
import sys
input = sys.stdin.readline

n, m = map(int, input().split())  # 노드 수, 간선 수
edges = [tuple(map(int, input().split())) for _ in range(m)]

graph = build_graph_list(n, edges)

 

- 트리

• 간선 저장
• 가중치 유무 범용
• sys.setrecursionlimit(10**6) : 깊은 DFS(재귀) 대비용 깊이 설정

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input().strip())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]

tree = build_tree_list(n, edges) # 트리 생성 (아래 참고)

※ 대부분의 DFS, BFS, 트리 지름, 루트 찾기 등 문제에서는 가중치 없는 버전으로 충분

 

- 내장 함수 input 사용

• 사용자 안내 메시지 출력
• 가중치 없는 그래프라면 w 제외 (가중치 유무 범용 X)

N, E = map(int, input("노드 개수와 간선 개수를 입력하세요 (예: 5 4): ").split())
directed = input("유향 그래프인가요? (y/n): ").strip().lower() == 'y'

edges = []
print("간선 정보를 입력하세요 (예: 1 2 10):")
for _ in range(E):
    u, v, w = input().split()
    w = int(w)  # 가중치는 정수 변환
    edges.append((u, v, w))

 

 

2. 그래프 생성 함수

 

(공통) 인접 리스트 형태로 변환해 무방향/유향 그래프 생성

• 저장된 간선 사용, list 기반 인접 리스트(adj-list) 함수 (함수화)
• 노드 번호가 1번부터 n번까지 정수라고 가정
  →  빈 배열 생성시, 1번 노드부터 사용하므로 n+1
  → 고정된 정점 수이기 때문에, [[] for _ in range(N+1)] 방식이 직관적
• 노드 번호가 정수형 & 연속적일 때만 사용 가능
• 숫자 노드만 지원 (문자열은 지원 ❌)
  → 인덱스 접근은 정수만 가능 (list의 노드 키에 대한 제약 여부)
• 가중치 O/X 간선 처리 (가중치 없는 그래프라면 w 제외)
• 가장 빠르고 메모리 적게 사용

 

- 그래프 (인접 리스트, edges: [(u, v, w)] 형식)

def build_graph_list(n, edges):
    graph = [[] for _ in range(n + 1)] # 노드 연결 정보를 저장할 빈 리스트
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w)) # ➕ 무방향일때 추가
    return graph

 

- 트리

def build_tree_list(n, edges):
    tree = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        tree[u].append((v, w))
        tree[v].append((u, w))  # ➕ 무방향 트리
    return tree

 

- 간선을 따로 저장 없이 바로 생성

• 노드, 간선 수까지만 입력 받음
• for문을 통해 간선 입력과 동시에 생성

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))  # 무방향
return graph

 

 

3. 그래프 표현 방식 변경 (dict, defaultdict)

 

- dict 기반 인접 리스트 (인접 리스트, edges: [(u, v, w)] 형식)

• 문자열/숫자 노드 모두 지원
• 연속/불연속 상관없음
• 키 유무 수동 확인 필요 → if key not in graph 
• 약간 느림

def build_graph_dict(edges):
    graph = {}  # 인접 리스트 그래프

    for u, v, w in edges:
        # 딕셔너리의 리스트에 노드 추가
        if u not in graph:
            graph[u] = []
        graph[u].append((v, w))

        # ➕ 무방향(양방향) 일때 아래 추가
        if v not in graph:
            graph[v] = []
        graph[v].append((u, w))

    return graph

 

- defaultdict

• dict 장점 동일
• 초기화 자동 생성, 키 존재 자동 처리
  → defaultdict(list)는 처음 등장한 키에 자동으로 빈 리스트 []를 생성
• 약간 느림, 메모리 추가 사용
• 가장 간결, 동적 구성 → 에러 발생 가능성 거의 없음

from collections import defaultdict

def build_graph_defaultdict(edges):
    adj = defaultdict(list)
    
    for u, v in edges:
        adj[u].append(v)  # 출발점 정점
        adj[v].append(u)  # 도착점 정점, 방향 그래프인 경우 이 줄 제거
    
    return dict(adj)