페드로 파스칼까지 몇 다리? 실용적인 그래프 탐색으로 인맥 지도를 그려보자!

얼마 전 드라마 <더 만달로리안>을 보다가 문득, 제가 페드로 파스칼을 전혀 모른다는 사실에 깊은 슬픔을 느꼈습니다. 정말 비극적인 일이죠.

하지만 어쩌면 제가 아는 누군가가, 그 누군가가 아는 누군가가, 또 그 누군가가... 페드로 파스칼을 알고 있을 수도 있지 않을까요? 이 세상 어딘가에는 저와 그를 이어주는 유한한 소개의 사슬이 분명 존재할 겁니다. 그래서 오늘 우리가 해결해 볼 중요한 컴퓨터 과학 문제는 바로 이것입니다: 과연 페드로 파스칼에게 닿으려면 몇 번의 소개가 필요할까?

Image description

이런! 어쩌다 보니 우리는 그래프 문제를 만들어버렸네요!

당신의 소셜 라이프를 그래프로 바꿔보자

지구상의 모든 사람을 하나의 노드(node), 그리고 두 사람 사이의 모든 관계나 지인을 엣지(edge) 라고 상상해 보세요.

Alexandra ── Maria ── Sofia ── Pedro
    │
    └── John ── Elena ── Carlos

이것은 비가중치(unweighted) 이면서 무방향(undirected) 그래프입니다.

비가중치는 모든 연결의 중요도가 동일하다는 뜻입니다. 마리아가 소피아의 '절친'이든, 카페에서 '한 번 만난 사이'든, 그 중요도는 똑같이 1로 계산됩니다.
무방향은 관계가 양방향이라는 의미입니다. 알렉산드라가 마리아를 안다면, 마리아도 알렉산드라를 아는 것이죠.

원본 질문의 불필요한 수식어를 걷어내면, 문제는 "페드로 파스칼을 어떻게 만날까?"에서 "주어진 비가중치 그래프에서 노드 A와 노드 B 사이의 최단 경로는 무엇인가?"로 바뀌게 됩니다. 트리나 그래프에 익숙하신 분들이라면 바로 BFS(너비 우선 탐색, Breadth-First Search) 가 떠오르실 겁니다.

코드에서 이런 종류의 데이터를 표현하는 가장 간단한 방법은 바로 인접 리스트(adjacency list) 입니다.

const graph = {
  Alexandra: ["Maria", "John"],
  Maria: ["Alexandra", "Sofia"],
  Sofia: ["Maria", "Pedro"],
  Pedro: ["Sofia"],
  John: ["Alexandra", "Elena"],
  Elena: ["John", "Carlos"],
  Carlos: ["Elena"],
};

제가 실무에서 대규모 사용자 관계를 모델링하거나 마이크로서비스 간의 의존성을 파악할 때 이런 인접 리스트 방식이 메모리 효율성 면에서 얼마나 유용한지 직접 체감했죠. 특정 노드와 연결된 엣지만 저장하기 때문에 필요한 정보만 빠르게 접근할 수 있거든요.

우리의 망상에 알고리즘을 입히자

안타깝게도 허공에 대고 "혹시 페드로 파스칼 아는 사람?!"하고 외치는 것은 알고리즘이 아닙니다. 순서도, 기억도, 종료 조건도 없으니까요. 그냥 끌리는 대로 이 사람 저 사람 찾아다니다 보면 이런 상황이 쉽게 발생할 수 있습니다:

Alexandra → Maria → Sofia → Maria → Sofia → Maria → ...

그래프가 무방향이기 때문에 마리아는 소피아로 연결되고, 소피아는 다시 마리아로 연결될 수 있습니다. 우리가 이미 방문했던 사람을 기억하지 못하면, 영원히 같은 사람들을 다시 찾아다니는 것을 막을 방법이 없습니다.

따라서 우리에게는 기본적으로 두 가지가 필요합니다.

사람들을 탐색할 순서 규칙.
이미 방문한 사람들을 기억하는 방법.

바로 여기서 큐(Queue)와 방문한 노드 집합(Visited Set)이 등장합니다.

너비 우선 탐색(BFS) 설명

최단 경로를 찾는 핵심 아이디어는 이것입니다: 두 연결만큼 떨어진 사람을 확인하기 전에, 한 연결만큼 떨어진 모든 사람을 먼저 확인한다. 이것이 바로 너비 우선 탐색이며, 그래프를 마치 레벨별로 정리하듯 탐색합니다.

Level 0        Alexandra
                  │
           ┌──────┴──────┐
Level 1   Maria          John
            │              │
Level 2   Sofia          Elena
            │
Level 3   PEDRO 🎉

BFS는 먼저 나의 직접적인 친구들(레벨 1)을 모두 확인합니다. 만약 페드로가 거기 없다면 (🥲), 그 다음으로 나의 직접적인 친구들의 직접적인 친구들(레벨 2)을 모두 확인하는 식으로 진행됩니다. 페드로가 발견되는 순간, 그것이 가능한 가장 짧은 경로라는 것을 알 수 있습니다. 왜냐하면 그보다 짧은 경로는 이미 모두 확인했기 때문이죠.

모든 것을 한데 모으기


function introductionsAway(graph, start, target) {
  // 시작 지점과 목표 지점이 같다면 0단계, 자기 자신
  if (start === target) return { degrees: 0, path: [start] };

  // 이미 방문한 노드를 기록하는 집합
  const visited = new Set([start]);
  // 탐색할 노드와 그 노드까지의 경로를 저장하는 큐
  // 각 요소는 [현재 사람, 현재까지의 경로] 형태
  const queue = [[start, [start]]]; 

  // 큐가 비어있지 않은 동안 반복
  while (queue.length > 0) {
    // 큐에서 가장 오래된 요소를 꺼냄 (FIFO)
    const [person, path] = queue.shift();

    // 현재 사람의 친구들을 순회
    for (const friend of graph[person] || []) { // 해당 사람이 친구가 없을 경우를 대비해 || [] 추가
      // 이미 방문한 친구라면 건너뜀
      if (visited.has(friend)) continue;
      // 친구가 목표 지점이라면 최단 경로를 찾은 것
      if (friend === target) {
        return { degrees: path.length, path: [...path, friend] };
      }

      // 친구를 방문한 노드로 추가하고 큐에 넣음
      visited.add(friend);
      queue.push([friend, [...path, friend]]);
    }
  }

  // 목표 지점에 도달할 수 없다면 -1 반환
  return { degrees: -1, path: [] };
}

이 코드를 사용하면 introductionsAway(graph, "Alexandra", "Pedro")는 { degrees: 3, path: ["Alexandra", "Maria", "Sofia", "Pedro"] }를 반환할 겁니다. 저의 페드로 파스칼까지의 소개는 최소 3번이 필요하다는 뜻이죠!

반전: 실제 관계는 똑같지 않다

지금까지 우리의 문제에서 '누군가를 안다'는 것은 이진법적인 문제였습니다. 하지만 당신과 저 모두 그것이 거짓이라는 것을 알죠. "마리아가 페드로 옆에 한 번 서 있었다"는 것과, "페드로? 아, 우리 매주 목요일 저녁 같이 먹어" 사이에는 너~무 큰 차이가 있습니다.

기술적으로는 둘 다 관계지만, 실질적으로는 후자가 제 '임무'에 훨씬 더 유용할 겁니다.

Alexandra --2-- Maria --5-- Sofia --4-- Tessa --1-- Pedro

그래서 각 관계에 '소개 비용(introduction cost)'을 할당해 봅시다. 친밀한 관계는 소개를 부탁하기 쉽기 때문에 비용이 낮고, 약한 지인은... 뭐, 행운을 빌죠. 비용이 높을 겁니다.

하지만 BFS 알고리즘은 이렇게 가중치가 부여된 관계는 처리할 줄 모릅니다. 가중치 그래프의 경우, 우리는 다익스트라 알고리즘(Dijkstra's algorithm) 에 주목해야 합니다.

다익스트라 알고리즘, 간단히

다익스트라 알고리즘은 살짝 다른 질문을 합니다:

"A에서 B까지 가는 가장 저렴한(cheapest) 경로는 무엇인가?"

우리가 노드를 발견한 순서대로 탐색하는 대신, 다익스트라 알고리즘은 시작 지점으로부터 현재까지 누적된 비용이 가장 낮은 노드를 우선적으로 탐색합니다.

이는 보통 BFS의 일반적인 큐를 우선순위 큐(priority queue) 로 대체하는 것을 의미합니다.

같은 그래프, 다른 명칭

페드로 파스칼 상황은 좀 우스꽝스럽다는 것을 저도 압니다. 하지만 그 밑바탕에 깔린 문제는 전혀 그렇지 않죠. 노드와 엣지가 나타내는 대상을 바꾸면, 같은 아이디어가 어디에나 나타납니다.

도메인	노드	엣지	"최단 경로"가 답하는 질문
소셜 그래프	사람	관계	"페드로 파스칼까지 몇 번의 소개가 필요할까?"
지도 / GPS	교차로	도로 (시간/거리에 따라 가중치 부여)	"A에서 B까지 가장 빠른 길은?"
웹 크롤링	웹 페이지	하이퍼링크	"이 페이지에서 저 페이지까지 몇 번 클릭해야 할까?"
코드 베이스	모듈/파일	임포트/의존성	"이 파일을 바꾸면 무엇이 깨질까?"
추천 시스템	사용자 또는 아이템	유사성/상호작용 강도	"이 사용자에게 가장 관련성 높은 것은 무엇일까?"

그래프는 처음 접했을 때는 복잡하고 이해하기 어려운 컴퓨터 과학 개념 중 하나입니다. 노드, 엣지, 순회, 큐... 대학교 때 처음 그래프 이론을 접했을 땐 그저 복잡한 이론이라고만 생각했는데, 막상 현업에서 시스템 아키텍처나 데이터 흐름을 설계할 때면 그래프 사고방식이 정말 큰 도움이 되더라고요. 특히 의존성 관리나 최적화 문제에서 빛을 발하죠.

결국 이 모든 것들은 어디에나 존재합니다. 인터넷 그 자체도 사실은 거대한 그래프라고 볼 수 있죠.

아, 혹시라도 페드로 파스칼을 아는 사람을 아는 사람을 아는 사람이 있다면... 언제든지 저에게 연락 주세요!

원문: https://dev.to/ale3oula/how-many-introductions-away-are-you-from-pedro-pascal-a-practical-introduction-to-graph-search-5bfg 수집일: 2026-08-13 00:54:45