WeniVooks

검색
북마크 이동

코딩 테스트 에센셜 with 자바스크립트

그래프

그래프와 트리 문제는 풀이가 매우 유사합니다. 연습문제는 별도로 없습니다.

1. 그래프 (Graph)

그래프는 노드(정점)와 간선으로 이루어진 자료구조로, 노드 간의 관계를 표현합니다. 트리와 달리 사이클이 있을 수 있고, 방향성이 있을 수도 있습니다.

1.1 그래프의 기본 용어
  • 정점(Vertex): 노드, 데이터를 저장하는 위치
  • 간선(Edge): 정점들을 연결하는 선
  • 인접(Adjacent): 두 정점이 간선으로 연결된 관계
  • 차수(Degree): 정점에 연결된 간선의 수
  • 경로(Path): 한 정점에서 다른 정점으로 가는 간선의 순서
  • 사이클(Cycle): 시작 정점과 끝 정점이 같은 경로
1.2 그래프의 종류
1.2.1 방향 그래프 vs 무방향 그래프
  • 무방향 그래프 (Undirected Graph): 간선에 방향이 없음 (양방향 통행 가능)
  • 방향 그래프 (Directed Graph): 간선에 방향이 있음 (단방향 통행)
1.2.2 가중치 그래프

간선에 비용/거리/시간 등의 가중치(Weight)가 있는 그래프입니다.

1.2.3 연결 그래프 vs 비연결 그래프
  • 연결 그래프: 모든 정점 사이에 경로가 존재
  • 비연결 그래프: 일부 정점 사이에 경로가 없음
1.3 그래프 표현 방법
1.3.1 인접 행렬 (Adjacency Matrix)

2차원 배열로 그래프를 표현합니다.

// 무방향 그래프 예제
// 0 - 1
// |   |
// 2 - 3
 
// 인접 행렬 (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와 연결
];
 
// 가중치 그래프 (Infinity는 연결 안됨을 의미)
const weightedGraph = [
    [0,        5,        Infinity, 1],
    [5,        0,        3,        7],
    [Infinity, 3,        0,        2],
    [1,        7,        2,        0]
];
 
// 연결 확인
if (graph[0][1] === 1) {
    console.log("0과 1은 연결되어 있음");
}
 
// 인접한 정점 찾기
function getNeighborsMatrix(graph, v) {
    // 인접 행렬에서 정점 v의 인접 정점들 반환
    const neighbors = [];
    for (let i = 0; i < graph[v].length; i++) {
        if (graph[v][i] !== 0) {
            neighbors.push(i);
        }
    }
    return neighbors;
}
 
console.log(getNeighborsMatrix(graph, 0));  // [1, 2]
// 무방향 그래프 예제
// 0 - 1
// |   |
// 2 - 3
 
// 인접 행렬 (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와 연결
];
 
// 가중치 그래프 (Infinity는 연결 안됨을 의미)
const weightedGraph = [
    [0,        5,        Infinity, 1],
    [5,        0,        3,        7],
    [Infinity, 3,        0,        2],
    [1,        7,        2,        0]
];
 
// 연결 확인
if (graph[0][1] === 1) {
    console.log("0과 1은 연결되어 있음");
}
 
// 인접한 정점 찾기
function getNeighborsMatrix(graph, v) {
    // 인접 행렬에서 정점 v의 인접 정점들 반환
    const neighbors = [];
    for (let i = 0; i < graph[v].length; i++) {
        if (graph[v][i] !== 0) {
            neighbors.push(i);
        }
    }
    return neighbors;
}
 
console.log(getNeighborsMatrix(graph, 0));  // [1, 2]

특징:

  • 공간복잡도: O(V²) (V는 정점 수)
  • 연결 확인: O(1)
  • 모든 간선 확인: O(V²)
  • 희소 그래프에서 비효율적 (간선이 적으면 0이 많음)
1.3.2 인접 리스트 (Adjacency List)

각 정점의 인접 정점들을 리스트로 저장합니다.

// 무방향 그래프
// 0 - 1
// |   |
// 2 - 3
 
// 인접 리스트 (객체)
const graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
};
 
// 또는 배열의 배열
const graphList = [
    [1, 2],     // 0번 정점
    [0, 3],     // 1번 정점
    [0, 3],     // 2번 정점
    [1, 2]      // 3번 정점
];
 
// 가중치 그래프 (정점, 가중치) 배열로 저장
const weightedGraph = {
    0: [[1, 5], [3, 1]],
    1: [[0, 5], [2, 3], [3, 7]],
    2: [[1, 3], [3, 2]],
    3: [[0, 1], [1, 7], [2, 2]]
};
 
// 인접한 정점 찾기
function getNeighborsList(graph, v) {
    // 인접 리스트에서 정점 v의 인접 정점들 반환
    return graph[v];
}
 
console.log(getNeighborsList(graph, 0));  // [1, 2]
// 무방향 그래프
// 0 - 1
// |   |
// 2 - 3
 
// 인접 리스트 (객체)
const graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
};
 
// 또는 배열의 배열
const graphList = [
    [1, 2],     // 0번 정점
    [0, 3],     // 1번 정점
    [0, 3],     // 2번 정점
    [1, 2]      // 3번 정점
];
 
// 가중치 그래프 (정점, 가중치) 배열로 저장
const weightedGraph = {
    0: [[1, 5], [3, 1]],
    1: [[0, 5], [2, 3], [3, 7]],
    2: [[1, 3], [3, 2]],
    3: [[0, 1], [1, 7], [2, 2]]
};
 
// 인접한 정점 찾기
function getNeighborsList(graph, v) {
    // 인접 리스트에서 정점 v의 인접 정점들 반환
    return graph[v];
}
 
console.log(getNeighborsList(graph, 0));  // [1, 2]

특징:

  • 공간복잡도: O(V + E) (V는 정점 수, E는 간선 수)
  • 연결 확인: O(degree) (정점의 차수만큼)
  • 모든 간선 확인: O(V + E)
  • 희소 그래프에서 효율적

인접 행렬 vs 인접 리스트 선택 기준

인접 행렬을 사용할 때:

  • 그래프가 밀집(Dense)할 때 (간선이 많을 때)
  • 두 정점 간 연결 여부를 자주 확인할 때
  • 정점의 수가 적을 때

인접 리스트를 사용할 때:

  • 그래프가 희소(Sparse)할 때 (간선이 적을 때)
  • 모든 인접 정점을 순회할 때
  • 메모리를 절약해야 할 때
  • 대부분의 코딩테스트 문제 (일반적으로 희소 그래프)

2. 그래프 탐색

그래프의 모든 정점을 체계적으로 방문하는 방법입니다. 트리 챕터에서 학습한 DFS와 BFS를 그래프에 적용합니다.

트리 vs 그래프 탐색 차이

트리 탐색 (이전 챕터):

  • 루트에서 시작하여 자식 노드 탐색
  • 사이클이 없어 방문 체크 선택적
  • 부모-자식 관계가 명확

그래프 탐색 (현재 챕터):

  • 임의의 정점에서 시작 가능
  • 사이클이 있어 반드시 방문 체크 필요
  • 양방향 간선도 가능
2.1 그래프에서 DFS 구현

트리와 달리 그래프는 사이클이 있을 수 있으므로 방문 체크가 필수입니다.

2.1.1 DFS 재귀 구현
function dfsRecursive(graph, start, visited = new Set()) {
    // 그래프 DFS 재귀 구현
    // 시간복잡도: O(V + E)
    // 공간복잡도: O(V)
 
    visited.add(start);
    console.log(start);
 
    // 인접한 정점 중 방문하지 않은 정점 탐색
    for (const neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
 
    return visited;
}
 
// 테스트 (무방향 그래프)
const graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
};
 
dfsRecursive(graph, 1);  // 1 2 4 5 3
function dfsRecursive(graph, start, visited = new Set()) {
    // 그래프 DFS 재귀 구현
    // 시간복잡도: O(V + E)
    // 공간복잡도: O(V)
 
    visited.add(start);
    console.log(start);
 
    // 인접한 정점 중 방문하지 않은 정점 탐색
    for (const neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
 
    return visited;
}
 
// 테스트 (무방향 그래프)
const graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
};
 
dfsRecursive(graph, 1);  // 1 2 4 5 3
2.1.2 DFS 스택 구현
function dfsStack(graph, start) {
    // 그래프 DFS 스택 구현
    // 시간복잡도: O(V + E)
    // 공간복잡도: O(V)
 
    const visited = new Set();
    const stack = [start];
 
    while (stack.length > 0) {
        const node = stack.pop();
 
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node);
 
            // 인접한 정점을 역순으로 스택에 추가
            const neighbors = graph[node] || [];
            for (let i = neighbors.length - 1; i >= 0; i--) {
                const neighbor = neighbors[i];
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
 
    return visited;
}
 
// 테스트
dfsStack(graph, 1);  // 1 2 4 5 3
function dfsStack(graph, start) {
    // 그래프 DFS 스택 구현
    // 시간복잡도: O(V + E)
    // 공간복잡도: O(V)
 
    const visited = new Set();
    const stack = [start];
 
    while (stack.length > 0) {
        const node = stack.pop();
 
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node);
 
            // 인접한 정점을 역순으로 스택에 추가
            const neighbors = graph[node] || [];
            for (let i = neighbors.length - 1; i >= 0; i--) {
                const neighbor = neighbors[i];
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
 
    return visited;
}
 
// 테스트
dfsStack(graph, 1);  // 1 2 4 5 3
2.2 그래프에서 BFS 구현

BFS는 최단 경로를 보장하므로 가중치가 없는 그래프에서 최단 거리 문제에 자주 사용됩니다.

function bfs(graph, start) {
    // 그래프 BFS 구현
    // 시간복잡도: O(V + E)
    // 공간복잡도: O(V)
 
    const visited = new Set();
    const queue = [start];
    visited.add(start);
 
    while (queue.length > 0) {
        const node = queue.shift();
        console.log(node);
 
        // 인접한 정점 중 방문하지 않은 정점을 큐에 추가
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
 
    return visited;
}
 
// 테스트
const graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
};
 
bfs(graph, 1);  // 1 2 3 4 5
function bfs(graph, start) {
    // 그래프 BFS 구현
    // 시간복잡도: O(V + E)
    // 공간복잡도: O(V)
 
    const visited = new Set();
    const queue = [start];
    visited.add(start);
 
    while (queue.length > 0) {
        const node = queue.shift();
        console.log(node);
 
        // 인접한 정점 중 방문하지 않은 정점을 큐에 추가
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
 
    return visited;
}
 
// 테스트
const graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
};
 
bfs(graph, 1);  // 1 2 3 4 5
2.3 DFS vs BFS 활용
특성DFSBFS
자료구조스택 (재귀)큐
탐색 방식깊이 우선너비 우선
경로 탐색모든 경로 탐색최단 경로 탐색
메모리낮음 (경로 길이)높음 (같은 레벨 모두 저장)
시간복잡도O(V + E)O(V + E)
그래프 활용사이클 검사, 위상 정렬, 연결 요소최단 거리, 레벨별 처리

그래프 탐색 선택 가이드

DFS를 사용할 때:

  • 모든 경로를 탐색해야 할 때
  • 백트래킹 문제 (미로 찾기, 조합 생성)
  • 사이클 검사
  • 위상 정렬
  • 연결 요소(Connected Component) 찾기

BFS를 사용할 때:

  • 최단 경로를 찾을 때 (가중치 없는 그래프)
  • 레벨별로 처리해야 할 때
  • 시작점에서 가까운 정점부터 탐색할 때
  • 최소 이동 횟수 구하기

3. 그래프 사용 시나리오

3.1 그래프를 사용하는 경우

  • 네트워크 모델링

    • 소셜 네트워크, 컴퓨터 네트워크, 교통 네트워크

  • 경로 찾기

    • 최단 경로 (다익스트라, 벨만-포드)
    • 모든 쌍 최단 경로 (플로이드-워셜)
    • 내비게이션

  • 연결 관계 분석

    • 친구 관계, 추천 시스템
    • 연결 요소 찾기

  • 상태 전이

    • 게임 AI, 프로세스 관리

  • 의존성 관리

    • 작업 순서 (위상 정렬)
    • 패키지 의존성
3.2 그래프 알고리즘 분류
알고리즘목적시간복잡도
DFS경로 탐색, 사이클 검사O(V + E)
BFS최단 경로 (무가중치)O(V + E)
다익스트라최단 경로 (양의 가중치)O((V + E) log V)
벨만-포드최단 경로 (음의 가중치)O(VE)
플로이드-워셜모든 쌍 최단 경로O(V³)
크루스칼최소 신장 트리O(E log E)
프림최소 신장 트리O(E log V)
위상 정렬순서 결정O(V + E)
3.4 트리3.6 힙