🔤 문자열 정점 입력에 대응하는 그래프 알고리즘 설계법

---

✅ 왜 문자열 입력이 문제인가?

대부분의 그래프 알고리즘은 정점을 숫자(0부터 N-1)로 다룬다.
하지만 실전 문제에서는 정점이 아래처럼 문자열로 주어지는 경우가 많다:

# 예시 입력
3
A B
B C
C A

→ 이럴 때는 기존의 parent[0], graph[1] 같은 배열 접근 방식이 불가능
→ 반드시 문자열 → 숫자 매핑 또는 dict 기반 구조로 바꿔야 한다.

---

✅ 대응 전략 2가지

방식	설명	장점	단점
딕셔너리 기반 처리	dict["A"]처럼 직접 접근	가독성 높음	느릴 수 있음
문자열 → 숫자 매핑	A → 0, B → 1 등 인덱스로 치환	기존 코드 그대로 사용 가능	초기 변환 필요

---

✅ 매핑 기초 (공통 템플릿)

names = sorted(list(set(all_node_names)))
name_to_idx = {name: idx for idx, name in enumerate(names)}
idx_to_name = {idx: name for name, idx in name_to_idx.items()}

---

✅ 알고리즘별 문자열 입력 대응 예시

1. DFS / BFS

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"]
}

visited = set()

def dfs(node):
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs(neighbor)

dfs("A")

✔️ visited를 set으로 두면 문자열도 바로 대응 가능

2. 연결 요소 찾기

components = []
visited = set()

for node in graph:
    if node not in visited:
        comp = []
        def dfs(n):
            visited.add(n)
            comp.append(n)
            for nxt in graph[n]:
                if nxt not in visited:
                    dfs(nxt)
        dfs(node)
        components.append(comp)

print(components)

✔️ 문자열 정점에도 바로 DFS/BFS 사용 가능

3. 유니온 파인드

parent = {node: node for node in nodes}

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    root_a = find(a)
    root_b = find(b)
    if root_a != root_b:
        parent[root_b] = root_a

✔️ dict로 관리하면 문자열 기반도 무리 없이 작동

4. 사이클 탐지 (무방향 그래프, DFS)

def has_cycle(node, parent, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle(neighbor, node, visited):
                return True
        elif neighbor != parent:
            return True
    return False

✔️ DFS + parent 추적도 문자열 그대로 가능

5. MST (Kruskal)

edges = [("A", "B", 3), ("B", "C", 1), ("A", "C", 2)]
nodes = set()
for u, v, _ in edges:
    nodes.add(u)
    nodes.add(v)

# 유니온 파인드 초기화
parent = {node: node for node in nodes}

edges.sort(key=lambda x: x[2])
mst = []

for u, v, cost in edges:
    if find(u) != find(v):
        union(u, v)
        mst.append((u, v, cost))

✔️ 간선 리스트 기반 MST는 문자열 정점 그대로 정렬하고 처리 가능

6. 위상 정렬 (진입차수 기반)

from collections import deque, defaultdict

graph = defaultdict(list)
indegree = defaultdict(int)
nodes = set()

for a, b in prerequisites:
    graph[a].append(b)
    indegree[b] += 1
    nodes |= {a, b}

q = deque([n for n in nodes if indegree[n] == 0])
res = []

while q:
    node = q.popleft()
    res.append(node)
    for nxt in graph[node]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            q.append(nxt)

✔️ defaultdict와 set 활용하면 가독성 좋게 위상 정렬 가능

7. 최단 경로 (다익스트라)

import heapq

graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)],
    "D": []
}

def dijkstra(start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, now = heapq.heappop(pq)
        if d > dist[now]: continue
        for nxt, cost in graph[now]:
            if dist[now] + cost < dist[nxt]:
                dist[nxt] = dist[now] + cost
                heapq.heappush(pq, (dist[nxt], nxt))

    return dist

print(dijkstra("A"))

---

✅ 마무리 요약

알고리즘	문자열 처리 방식
DFS / BFS	visited = set / dict 사용
연결 요소	DFS 그대로 사용 가능
유니온 파인드	parent = {name: name}
사이클 탐지	DFS with parent (문자 그대로 가능)
MST (Kruskal)	간선 정렬 + 문자열 유니온 파인드
위상 정렬	defaultdict, set, deque 활용
다익스트라	dist = {} + heapq

문자열 정점 입력도 전혀 문제없다.
dict, set, defaultdict를 자유자재로 활용하고
필요하면 문자 → 숫자 인덱스 매핑만 잘 해두면
어떤 그래프 문제든 알고리즘을 그대로 적용할 수 있다.