034. 그래프 탐색기

[문제] 노드(점)와 간선(점을 잇는 선)으로 이루어진 그래프를 다루는 MCP 서버를 구현한다. 간선은 방향이 없는 양방향이다. 즉 A와 B를 잇는 간선이 있으면 A에서 B로도, B에서 A로도 갈 수 있다. 그래프는 인접 리스트(각 노드마다 "직접 연결된 이웃 노드들의 목록"을 들고 있는 형태)로 관리한다고 생각하면 된다. BFS(너비 우선 탐색)란 시작 노드에서 가까운 노드부터 차례로 방문하는 탐색 방법이다. 한 노드를 방문하면 그 노드의 이웃들을 먼저 모두 큐에 넣고, 그 다음 단계의 노드들로 넘어간다. 최단 경로란 시작 노드에서 끝 노드까지 거쳐 가는 노드 수가 가장 적은 경로를 말한다. [구현할 함수] - add_edge(node1: str, node2: str) -> int node1 과 node2 를 잇는 양방향 간선을 추가하고, 추가 후 그래프 전체의 간선 수를 반환한다. - bfs(start_node: str) -> List[str] start_node 부터 BFS로 방문한 노드들을 방문 순서대로 담은 배열을 반환한다. 한 노드의 이웃을 방문할 때는 알파벳 오름차순으로 방문한다. start_node 가 그래프에 없으면 빈 배열을 반환한다. - shortest_path(start: str, end: str) -> List[str] start 에서 end 까지의 최단 경로를 노드 배열(start 와 end 포함)로 반환한다. 경로가 없거나 노드가 그래프에 없으면 빈 배열을 반환한다. [입력·상태] 서버 인스턴스 내부에 그래프(노드별 이웃 목록)를 유지한다. 초기 상태는 노드도 간선도 없는 빈 그래프다. [제약] - 노드 이름은 문자열이다. - BFS에서 이웃 방문 순서는 알파벳 오름차순으로 고정한다(결과가 결정론적이도록). - 존재하지 않는 노드/경로에 대한 조회는 빈 배열을 반환한다. [예시] (각각 초기 빈 상태에서의 단일 호출) add_edge("A", "B") -> 1 # 간선 1개 추가됨 bfs("A") -> [] # A 노드 자체가 없는 빈 그래프 shortest_path("A", "C") -> [] # 그래프가 비어 경로 없음