그래프(Graph): 지하철 노선도와 우리 사이

프롤로그 - "여기서 강남역까지 어떻게 가요?"

처음 서울 지하철을 탔을 때, 노선도를 보고 멘붕이 왔습니다.

"2호선 타고 가다가 3호선으로 갈아타고... 어? 4호선도 되네? 근데 뭐가 제일 빨라?"

시니어: "그거 그래프야. 역(정점)이랑 노선(간선)으로 된. 컴퓨터는 저걸 자료구조로 표현해서 최단 경로를 찾아."

저: "그래프가 뭔데요? 엑셀 차트 같은 거요?"

시니어: (한숨) "아니... 자료구조 그래프... 배열이나 트리처럼 데이터를 저장하는 방식이야."

저: "트리랑 뭐가 달라요? 둘 다 점이랑 선으로 된 거 같은데?"

시니어: "트리는 부모-자식 관계가 명확하고 사이클이 없어. 근데 그래프는 친구 관계처럼 평등하고, 순환도 가능해. 철수가 영희 친구, 영희가 민수 친구, 민수가 다시 철수 친구... 이렇게."

그때 깨달았습니다. 세상의 대부분 관계는 트리보다 그래프에 가깝다는 걸.

왜 공부하게 되었나

회사에서 "친구 추천" 기능을 만들라는 업무를 받았습니다.

요구사항:

1. 내 친구의 친구를 추천해줘.
2. 이미 내 친구인 사람은 제외.
3. 공통 친구가 많을수록 우선 추천.

저: "SQL로 JOIN 몇 번 하면 되지 않나요?"

시니어: "친구 1만 명 있는 사람은 어떻게 할 건데? 10억 행 JOIN할래?"

저: (침묵)

시니어: "이건 그래프 탐색 문제야. BFS 쓰면 레벨별로 탐색하면서 2촌까지만 효율적으로 찾을 수 있어. 그리고 인접 리스트로 구현하면 메모리도 훨씬 적게 쓰고."

그때부터 그래프를 제대로 공부했습니다. 단순히 개념이 아니라, 어떻게 구현하고 어떤 상황에서 어떤 방식을 써야 하는지까지.

처음엔 뭐가 이해가 안 갔나

• 트리랑 뭐가 다른 거야? 둘 다 노드랑 엣지로 연결된 건데?
• 인접 행렬? 인접 리스트? 뭐가 나아? 언제 뭘 써야 해?
• BFS, DFS가 뭔데? 왜 두 개나 있어? 차이가 뭐야?
• 메모리는 얼마나 먹어? 친구 1만 명이면 배열 크기가 어떻게 돼?
• 위상 정렬? 최소 신장 트리? 이름부터 어려워...

무엇보다 "왜 구현 방식이 이렇게 많아? 답이 하나가 아니네?"

깨달음의 순간 - "친구 관계에는 위계가 없다"

시니어가 화이트보드에 그려준 그림:

트리 (Tree):

회사 조직도
     사장
    /   \
  부장A  부장B
  /  \
과장 대리

"명확한 상하 관계. 순환(Cycle) 없음. 부모는 딱 1명."

그래프 (Graph):

페이스북 친구
철수 ─ 영희
 │      │
민수 ─ 수지

"평등한 관계. 순환 가능. 부모 자식 개념 없음."

시니어: "트리는 그래프의 특수한 경우야. N개 노드, N-1개 엣지, 사이클 없음, 연결됨. 이 4가지 조건 만족하면 트리."

"아, 트리는 그래프의 엄격한 버전이구나!" 이해했다.

깊이 파보기 1 - 인접 행렬 vs 인접 리스트 - 메모리 전쟁

여기서부터 실제이 시작됩니다. 그래프를 어떻게 메모리에 저장할 거냐?

인접 행렬 (Adjacency Matrix)

2차원 배열로 표현:

// 4명의 친구 관계 (무방향 그래프)
const graph = [
  [0, 1, 1, 0],  // 0번(철수): 1번, 2번과 친구
  [1, 0, 0, 1],  // 1번(영희): 0번, 3번과 친구
  [1, 0, 0, 1],  // 2번(민수): 0번, 3번과 친구
  [0, 1, 1, 0]   // 3번(수지): 1번, 2번과 친구
];

// 철수(0)와 영희(1)가 친구인지 확인
console.log(graph[0][1] === 1);  // true - O(1) 즉시 확인!

// 영희(1)의 모든 친구 찾기
const yeongHeeFriends = [];
for (let i = 0; i < graph[1].length; i++) {
  if (graph[1][i] === 1) {
    yeongHeeFriends.push(i);  // O(V) 시간 - 모든 정점 확인 필요
  }
}
console.log(yeongHeeFriends);  // [0, 3]

언제 인접 행렬이 이기는가?

1. 밀집 그래프 (Dense Graph): 엣지가 V² 에 가까울 때

   • 예: 소셜 네트워크에서 모든 사람이 거의 다 친구인 작은 그룹 (10명이 서로 다 친구)
   • 메모리: O(V²) → 10² = 100칸. 엣지: 45개. 공간 효율 45%

2. 빠른 엣지 확인이 중요할 때: "A와 B가 친구인가?" 같은 질문이 자주 일어날 때

   • O(1) 시간에 즉시 답변 가능
   • 게임에서 "이 캐릭터가 저 캐릭터를 볼 수 있나?" 같은 실시간 체크

3. 가중치 그래프: 거리나 비용을 배열 값으로 바로 저장

   const distances = [
     [0,   15, 20,  0],   // 철수 → 영희 15km, 민수 20km
     [15,  0,  0,   30],  // 영희 → 수지 30km
     [20,  0,  0,   25],
     [0,   30, 25,  0]
   ];
   

단점 (치명적):

• 공간: O(V²) → 친구 1만 명 = 1만 x 1만 = 1억 칸 = 400MB (int 기준)
• 친구 목록 얻기: O(V) → 모든 행 스캔 필요

인접 리스트 (Adjacency List)

각자 친구 목록만 저장:

// Map 또는 Object로 구현
const graph = new Map();
graph.set('철수', ['영희', '민수']);
graph.set('영희', ['철수', '수지']);
graph.set('민수', ['철수', '수지']);
graph.set('수지', ['영희', '민수']);

// 철수의 친구 목록 - O(1)
console.log(graph.get('철수'));  // ['영희', '민수']

// 철수와 영희가 친구인지 확인 - O(degree)
const isFriend = graph.get('철수').includes('영희');  // true
// degree = 해당 정점의 엣지 개수 (철수 친구 2명 → O(2))

언제 인접 리스트가 압승하는가?

1. 희소 그래프 (Sparse Graph): 대부분의 실제 상황

   • 페이스북: 평균 친구 338명 (2014년 기준). V = 30억, E = 30억 × 338 / 2
   • 행렬: 30억² = 9 × 10¹⁸ 칸 (불가능)
   • 리스트: 30억 + 30억 × 338 / 2 = 약 5천억 칸 (가능)

2. BFS/DFS 같은 탐색: 이웃 노드만 필요할 때

   // 인접 리스트: 철수 친구만 바로 접근
   const neighbors = graph.get('철수');  // ['영희', '민수']
   
   // 인접 행렬: 모든 사람 확인 필요
   for (let i = 0; i < matrix[0].length; i++) {
     if (matrix[0][i] === 1) neighbors.push(i);
   }
   

3. 동적 그래프: 친구 추가/삭제가 빈번할 때

   // 리스트: 배열에 push/filter
   graph.get('철수').push('지민');  // O(1)
   
   // 행렬: 새 사람 추가 시 전체 배열 재생성 필요
   

제가 받아들인 교훈: 실제로는 90% 이상 인접 리스트를 씁니다. 행렬은 알고리즘 문제 풀 때나 밀집 그래프일 때만.

깊이 파보기 2 - Graph 클래스 구현 - 풀 코드

이론은 그만, 진짜 동작하는 코드를 만들어봤습니다.

class Graph {
  constructor(directed = false) {
    this.adjacencyList = new Map();
    this.directed = directed;  // 방향/무방향 그래프
  }

  // 정점 추가
  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  // 간선 추가
  addEdge(v1, v2, weight = 1) {
    // 정점 없으면 먼저 생성
    this.addVertex(v1);
    this.addVertex(v2);

    // v1 → v2 추가
    this.adjacencyList.get(v1).push({ node: v2, weight });

    // 무방향이면 v2 → v1도 추가
    if (!this.directed) {
      this.adjacencyList.get(v2).push({ node: v1, weight });
    }
  }

  // 정점 삭제
  removeVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) return;

    // 이 정점을 가리키는 모든 엣지 제거
    for (let [v, edges] of this.adjacencyList) {
      this.adjacencyList.set(
        v,
        edges.filter(e => e.node !== vertex)
      );
    }

    // 정점 자체 삭제
    this.adjacencyList.delete(vertex);
  }

  // 간선 삭제
  removeEdge(v1, v2) {
    if (!this.adjacencyList.has(v1) || !this.adjacencyList.has(v2)) return;

    this.adjacencyList.set(
      v1,
      this.adjacencyList.get(v1).filter(e => e.node !== v2)
    );

    if (!this.directed) {
      this.adjacencyList.set(
        v2,
        this.adjacencyList.get(v2).filter(e => e.node !== v1)
      );
    }
  }

  // BFS 구현
  bfs(start) {
    const visited = new Set();
    const queue = [start];
    const result = [];

    visited.add(start);

    while (queue.length > 0) {
      const current = queue.shift();
      result.push(current);

      const neighbors = this.adjacencyList.get(current) || [];
      for (let edge of neighbors) {
        if (!visited.has(edge.node)) {
          visited.add(edge.node);
          queue.push(edge.node);
        }
      }
    }

    return result;
  }

  // DFS 구현 (반복문 버전)
  dfsIterative(start) {
    const visited = new Set();
    const stack = [start];
    const result = [];

    while (stack.length > 0) {
      const current = stack.pop();

      if (!visited.has(current)) {
        visited.add(current);
        result.push(current);

        const neighbors = this.adjacencyList.get(current) || [];
        // 역순으로 push (스택이라서 나중에 pop될 순서 조정)
        for (let i = neighbors.length - 1; i >= 0; i--) {
          if (!visited.has(neighbors[i].node)) {
            stack.push(neighbors[i].node);
          }
        }
      }
    }

    return result;
  }

  // DFS 구현 (재귀 버전)
  dfsRecursive(start, visited = new Set(), result = []) {
    visited.add(start);
    result.push(start);

    const neighbors = this.adjacencyList.get(start) || [];
    for (let edge of neighbors) {
      if (!visited.has(edge.node)) {
        this.dfsRecursive(edge.node, visited, result);
      }
    }

    return result;
  }

  // 경로 존재 여부 확인
  hasPath(start, end) {
    if (start === end) return true;

    const visited = new Set();
    const queue = [start];
    visited.add(start);

    while (queue.length > 0) {
      const current = queue.shift();

      const neighbors = this.adjacencyList.get(current) || [];
      for (let edge of neighbors) {
        if (edge.node === end) return true;

        if (!visited.has(edge.node)) {
          visited.add(edge.node);
          queue.push(edge.node);
        }
      }
    }

    return false;
  }

  // 그래프 출력
  print() {
    for (let [vertex, edges] of this.adjacencyList) {
      const edgeStr = edges.map(e => `${e.node}(${e.weight})`).join(', ');
      console.log(`${vertex} → ${edgeStr}`);
    }
  }
}

// 사용 예제
const g = new Graph(false);  // 무방향 그래프

g.addEdge('철수', '영희');
g.addEdge('철수', '민수');
g.addEdge('영희', '수지');
g.addEdge('민수', '수지');

console.log('그래프 구조:');
g.print();
// 철수 → 영희(1), 민수(1)
// 영희 → 철수(1), 수지(1)
// 민수 → 철수(1), 수지(1)
// 수지 → 영희(1), 민수(1)

console.log('BFS 탐색:', g.bfs('철수'));
// ['철수', '영희', '민수', '수지']

console.log('DFS 탐색:', g.dfsIterative('철수'));
// ['철수', '영희', '수지', '민수']

console.log('철수 → 수지 경로 존재?', g.hasPath('철수', '수지'));
// true

이 구현에서 배운 것들:

1. Map vs Object: Map이 더 깨끗. key로 객체도 쓸 수 있고, 크기 추적도 쉬움
2. visited Set이 핵심: 없으면 무한 루프 (사이클 때문)
3. BFS는 Queue, DFS는 Stack: 자료구조가 곧 알고리즘

깊이 파보기 3 - BFS 완벽 분석 - 레벨 추적

친구 추천 기능을 다시 봅시다. 이번엔 레벨별로 추적합니다.

class GraphWithLevels extends Graph {
  bfsWithLevels(start, maxLevel = Infinity) {
    const visited = new Set([start]);
    const queue = [{ node: start, level: 0 }];
    const levels = new Map();
    levels.set(start, 0);

    while (queue.length > 0) {
      const { node, level } = queue.shift();

      if (level >= maxLevel) continue;

      const neighbors = this.adjacencyList.get(node) || [];
      for (let edge of neighbors) {
        if (!visited.has(edge.node)) {
          visited.add(edge.node);
          levels.set(edge.node, level + 1);
          queue.push({ node: edge.node, level: level + 1 });
        }
      }
    }

    return levels;
  }

  // 친구 추천: 2촌까지만, 1촌 제외
  recommendFriends(userId) {
    const levels = this.bfsWithLevels(userId, 2);
    const recommendations = [];

    for (let [user, level] of levels) {
      if (level === 2) {  // 2촌만
        recommendations.push(user);
      }
    }

    return recommendations;
  }

  // 공통 친구 수 기반 추천
  recommendWithCommonFriends(userId) {
    const myFriends = new Set(
      this.adjacencyList.get(userId).map(e => e.node)
    );

    const candidates = new Map();  // 후보 → 공통 친구 수

    // 내 친구의 친구들 탐색
    for (let edge of this.adjacencyList.get(userId)) {
      const friend = edge.node;
      const friendsOfFriend = this.adjacencyList.get(friend) || [];

      for (let fofEdge of friendsOfFriend) {
        const fof = fofEdge.node;

        // 나 자신도 아니고, 이미 친구도 아니면
        if (fof !== userId && !myFriends.has(fof)) {
          candidates.set(fof, (candidates.get(fof) || 0) + 1);
        }
      }
    }

    // 공통 친구 수로 정렬
    return Array.from(candidates.entries())
      .sort((a, b) => b[1] - a[1])
      .map(([user, count]) => ({ user, commonFriends: count }));
  }
}

// 실제 사용
const social = new GraphWithLevels(false);

social.addEdge('나', '철수');
social.addEdge('나', '영희');
social.addEdge('철수', '민수');
social.addEdge('철수', '수지');
social.addEdge('영희', '민수');
social.addEdge('영희', '지민');

console.log('레벨별 관계:');
console.log(social.bfsWithLevels('나'));
// Map {
//   '나' => 0,
//   '철수' => 1, '영희' => 1,
//   '민수' => 2, '수지' => 2, '지민' => 2
// }

console.log('친구 추천 (2촌):');
console.log(social.recommendFriends('나'));
// ['민수', '수지', '지민']

console.log('공통 친구 기반 추천:');
console.log(social.recommendWithCommonFriends('나'));
// [
//   { user: '민수', commonFriends: 2 },  // 철수, 영희 공통
//   { user: '수지', commonFriends: 1 },  // 철수만
//   { user: '지민', commonFriends: 1 }   // 영희만
// ]

실제로 와닿은 부분: 페이스북은 정말 이렇게 합니다. 공통 친구 많을수록 상위 노출.

깊이 파보기 4 - DFS 응용 - 위상 정렬 (Topological Sort)

방향 그래프에서 순서를 정하는 문제입니다.

예시: 대학 과목 선수과목

자료구조 → 알고리즘
프로그래밍기초 → 자료구조
프로그래밍기초 → 운영체제
운영체제 → 시스템프로그래밍

"어떤 순서로 수강해야 해?"

class DirectedGraph extends Graph {
  constructor() {
    super(true);  // 방향 그래프
  }

  // 위상 정렬 (DFS 기반)
  topologicalSort() {
    const visited = new Set();
    const stack = [];

    const dfsHelper = (vertex) => {
      visited.add(vertex);

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (let edge of neighbors) {
        if (!visited.has(edge.node)) {
          dfsHelper(edge.node);
        }
      }

      // 후위 순회에서 스택에 추가
      stack.push(vertex);
    };

    // 모든 정점 탐색 (연결 안 된 컴포넌트 대비)
    for (let vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        dfsHelper(vertex);
      }
    }

    // 역순이 위상 정렬 결과
    return stack.reverse();
  }

  // 사이클 감지 (위상 정렬 가능 여부)
  hasCycle() {
    const visited = new Set();
    const recStack = new Set();  // 현재 재귀 스택

    const dfsHelper = (vertex) => {
      visited.add(vertex);
      recStack.add(vertex);

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (let edge of neighbors) {
        if (!visited.has(edge.node)) {
          if (dfsHelper(edge.node)) return true;
        } else if (recStack.has(edge.node)) {
          // 재귀 스택에 있다 = 사이클!
          return true;
        }
      }

      recStack.delete(vertex);  // 백트래킹
      return false;
    };

    for (let vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        if (dfsHelper(vertex)) return true;
      }
    }

    return false;
  }
}

// 과목 선수과목 그래프
const courses = new DirectedGraph();

courses.addEdge('프로그래밍기초', '자료구조');
courses.addEdge('프로그래밍기초', '운영체제');
courses.addEdge('자료구조', '알고리즘');
courses.addEdge('운영체제', '시스템프로그래밍');

console.log('수강 순서:');
console.log(courses.topologicalSort());
// ['프로그래밍기초', '운영체제', '자료구조', '시스템프로그래밍', '알고리즘']
// 또는 ['프로그래밍기초', '자료구조', '운영체제', '알고리즘', '시스템프로그래밍']
// (여러 답 가능)

console.log('사이클 있음?', courses.hasCycle());  // false

// 순환 선수과목 추가하면?
courses.addEdge('알고리즘', '프로그래밍기초');  // 앗!
console.log('이제 사이클 있음?', courses.hasCycle());  // true

실제 응용:

• 빌드 시스템 (Makefile, Webpack): 파일 A가 B에 의존 → 순서 정하기
• 작업 스케줄링: Task A 끝나야 Task B 시작
• 패키지 매니저 (npm, pip): 의존성 해결 순서

깊이 파보기 5 - 연결 요소 (Connected Components)

무방향 그래프에서 "몇 개의 독립된 그룹이 있나?"

class UndirectedGraph extends Graph {
  constructor() {
    super(false);  // 무방향
  }

  findConnectedComponents() {
    const visited = new Set();
    const components = [];

    const dfs = (start, component) => {
      visited.add(start);
      component.push(start);

      const neighbors = this.adjacencyList.get(start) || [];
      for (let edge of neighbors) {
        if (!visited.has(edge.node)) {
          dfs(edge.node, component);
        }
      }
    };

    for (let vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        const component = [];
        dfs(vertex, component);
        components.push(component);
      }
    }

    return components;
  }
}

// SNS에서 친구 그룹 찾기
const sns = new UndirectedGraph();

// 그룹 1
sns.addEdge('철수', '영희');
sns.addEdge('영희', '민수');

// 그룹 2 (독립적)
sns.addEdge('지민', '수지');

// 그룹 3 (혼자)
sns.addVertex('태형');

console.log('친구 그룹들:');
console.log(sns.findConnectedComponents());
// [
//   ['철수', '영희', '민수'],
//   ['지민', '수지'],
//   ['태형']
// ]

실제 응용: 네트워크 분석, 커뮤니티 발견, 이미지 세그멘테이션

깊이 파보기 6 - 최소 신장 트리 (MST) - 간단 소개

가중치 그래프에서 "모든 정점을 최소 비용으로 연결"

예시: 섬들을 다리로 연결하는데 건설 비용 최소화

// Kruskal 알고리즘 (간소화 버전)
class WeightedGraph extends Graph {
  getAllEdges() {
    const edges = [];
    const seen = new Set();

    for (let [v1, neighbors] of this.adjacencyList) {
      for (let { node: v2, weight } of neighbors) {
        const edgeKey = [v1, v2].sort().join('-');
        if (!seen.has(edgeKey)) {
          edges.push({ v1, v2, weight });
          seen.add(edgeKey);
        }
      }
    }

    return edges.sort((a, b) => a.weight - b.weight);
  }

  // 간단한 Union-Find (실제론 최적화 필요)
  kruskalMST() {
    const edges = this.getAllEdges();
    const mst = [];
    const parent = new Map();

    // 각 정점 자기 자신이 부모
    for (let vertex of this.adjacencyList.keys()) {
      parent.set(vertex, vertex);
    }

    const find = (v) => {
      if (parent.get(v) !== v) {
        parent.set(v, find(parent.get(v)));
      }
      return parent.get(v);
    };

    const union = (v1, v2) => {
      const root1 = find(v1);
      const root2 = find(v2);
      if (root1 !== root2) {
        parent.set(root1, root2);
        return true;
      }
      return false;
    };

    for (let { v1, v2, weight } of edges) {
      if (union(v1, v2)) {
        mst.push({ v1, v2, weight });
      }
    }

    return mst;
  }
}

// 섬 연결 문제
const islands = new WeightedGraph(false);

islands.addEdge('제주', '목포', 150);
islands.addEdge('제주', '부산', 280);
islands.addEdge('목포', '부산', 200);
islands.addEdge('목포', '여수', 50);
islands.addEdge('부산', '여수', 80);

console.log('최소 비용 다리:');
console.log(islands.kruskalMST());
// [
//   { v1: '목포', v2: '여수', weight: 50 },
//   { v1: '부산', v2: '여수', weight: 80 },
//   { v1: '제주', v2: '목포', weight: 150 }
// ]
// 총 비용: 280

결국 이거였다: 가장 싼 엣지부터 추가하되, 사이클 안 만들면 됨.

깊이 파보기 7 - 그래프 색칠 문제

"인접한 정점은 다른 색으로 칠하되, 최소 색 개수는?"

실제 예시: 시험 시간표 배정

class ColoringGraph extends Graph {
  greedyColoring() {
    const color = new Map();
    const vertices = Array.from(this.adjacencyList.keys());

    // 첫 정점은 색 0
    color.set(vertices[0], 0);

    for (let i = 1; i < vertices.length; i++) {
      const vertex = vertices[i];

      // 인접 정점들의 색 확인
      const neighbors = this.adjacencyList.get(vertex) || [];
      const usedColors = new Set();

      for (let edge of neighbors) {
        if (color.has(edge.node)) {
          usedColors.add(color.get(edge.node));
        }
      }

      // 사용 안 된 가장 작은 색 찾기
      let assignedColor = 0;
      while (usedColors.has(assignedColor)) {
        assignedColor++;
      }

      color.set(vertex, assignedColor);
    }

    return color;
  }
}

// 과목 시험 시간표 (같은 학생이 듣는 과목은 인접)
const exams = new ColoringGraph(false);

exams.addEdge('수학', '물리');     // 같은 학생이 수강
exams.addEdge('수학', '화학');
exams.addEdge('물리', '생물');
exams.addEdge('화학', '생물');
exams.addEdge('영어', '국어');

console.log('시험 시간 배정:');
const schedule = exams.greedyColoring();
for (let [exam, timeSlot] of schedule) {
  console.log(`${exam}: ${timeSlot}교시`);
}
// 수학: 0교시
// 물리: 1교시
// 화학: 1교시 (수학과 안 겹침)
// 생물: 0교시 (물리, 화학과 안 겹침)
// 영어: 0교시
// 국어: 1교시

최소 색 개수 = 최소 시험 일수

정리해본다 - 언제 뭘 쓰나

상황	표현 방식	알고리즘	시간 복잡도
희소 그래프 (SNS)	인접 리스트	BFS (친구 추천)	O(V + E)
밀집 그래프 (작은 완전 그래프)	인접 행렬	-	O(V²) 공간
최단 경로 (무가중치)	리스트	BFS	O(V + E)
최단 경로 (가중치)	리스트	Dijkstra	O((V + E) log V)
선수과목 순서	리스트	위상 정렬	O(V + E)
사이클 감지	리스트	DFS	O(V + E)
연결 요소 개수	리스트	DFS/BFS	O(V + E)
최소 비용 연결	리스트	Kruskal/Prim	O(E log E)
스케줄 배정	리스트	그래프 색칠	O(V² + E)

핵심: 거의 모든 경우 인접 리스트. BFS는 최단 거리, DFS는 경로 탐색/사이클.

마치며 - "결국 세상은 그래프였다"

처음엔 "지하철 노선도랑 내 코드랑 무슨 상관?"이라고 생각했습니다.

6개월 뒤 제가 그래프로 구현한 것들:

• 친구 추천 시스템 (BFS, 2촌 탐색)
• 소셜 피드 랭킹 (PageRank 변형)
• 작업 의존성 관리 (위상 정렬)
• 네트워크 장애 감지 (연결 요소)
• 배달 최단 경로 (Dijkstra)

정리해본다:

1. 트리 vs 그래프: 트리는 계층, 그래프는 관계
2. 행렬 vs 리스트: 실전은 90% 리스트 (희소 그래프)
3. BFS vs DFS: BFS는 레벨/최단, DFS는 깊이/사이클
4. visited Set 필수: 안 쓰면 무한 루프
5. 방향성 중요: 팔로우(방향) vs 친구(무방향)

와닿았던 순간: "모든 관계는 그래프다." 페이스북, 유튜브, 구글, 우버... 다 그래프로 돌아갑니다.

처음 보는 문제가 나와도, "정점이 뭐고 간선이 뭐지?"만 파악하면 답이 보입니다.

"어디서 많이 본 것 같은데?" → 그래프입니다.