그래프

관련 문제

문제	난이도	유형
1260번 — DFS와 BFS	실버 II	DFS/BFS 기본
2667번 — 단지번호붙이기	실버 I	연결 요소 탐색
2178번 — 미로 탐색	실버 I	BFS 최단거리
1389번 — 케빈 베이컨의 6단계 법칙	실버 II	BFS 거리 합
7562번 — 나이트의 이동	실버 I	BFS 최단거리

---

1. 그래프란?

노드(정점, Vertex) 와 간선(Edge) 으로 이루어진 자료구조다.
현실의 지하철 노선도, SNS 팔로우 관계, 도로망 등을 표현할 때 사용한다.

노드: 지하철역
간선: 역과 역 사이의 연결

---

2. 그래프의 종류

종류	설명	예시
무방향 그래프	간선에 방향 없음 (양방향)	친구 관계
방향 그래프 (DAG)	간선에 방향 있음 (단방향)	팔로우 관계
가중치 그래프	간선에 비용/거리 존재	도로 거리
비가중치 그래프	간선에 비용 없음	연결 여부만

---

3. 그래프 표현 방법

인접 리스트 (일반적으로 권장)

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) graph.add(new ArrayList<>());

// 무방향 그래프 — 양방향 추가
graph.get(a).add(b);
graph.get(b).add(a);

// 방향 그래프 — 단방향만 추가
graph.get(a).add(b);

장점	단점
메모리 효율적	두 노드 연결 여부 확인이 느림
간선 수가 적을 때 유리

인접 행렬

int[][] graph = new int[N + 1][N + 1];

// 무방향 그래프
graph[a][b] = 1;
graph[b][a] = 1;

// 방향 그래프
graph[a][b] = 1;

장점	단점
두 노드 연결 여부 O(1) 확인	메모리 낭비 (N² 공간)
구현이 단순	노드가 많으면 비효율적

---

4. 그래프 탐색 — DFS vs BFS

DFS (깊이 우선 탐색)

한 방향으로 끝까지 파고든 뒤 되돌아오며 탐색한다.

static boolean[] visited;
static List<List<Integer>> graph;

static void dfs(int node) {
    visited[node] = true;

    for (int i = 0; i < graph.get(node).size(); i++) {
        int next = graph.get(node).get(i);
        if (!visited[next]) {
            dfs(next);
        }
    }
}

BFS (너비 우선 탐색)

현재 노드에서 가까운 노드부터 탐색한다.

static boolean[] visited;
static List<List<Integer>> graph;

static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();

        for (int i = 0; i < graph.get(node).size(); i++) {
            int next = graph.get(node).get(i);
            if (!visited[next]) {
                visited[next] = true;
                queue.add(next);
            }
        }
    }
}

DFS vs BFS 선택 기준

상황	선택
최단거리, 최소 횟수	BFS
경로 존재 여부, 연결 요소 개수	DFS 또는 BFS
백트래킹, 순열/조합	DFS
사이클 감지	DFS

---

5. 격자 그래프 탐색 (2차원 배열)

코테에서 가장 자주 나오는 형태다. dx, dy 배열로 상하좌우 이동을 표현한다.

static int[] dx = {-1, 1, 0, 0};  // 상, 하, 좌, 우
static int[] dy = {0, 0, -1, 1};

// 범위 체크 + 방문 여부 확인
for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
        if (!visited[nx][ny]) {
            visited[nx][ny] = true;
            // 탐색 진행
        }
    }
}

---

6. 주요 용어 정리

용어	설명
정점 (Vertex)	그래프의 노드
간선 (Edge)	노드 사이의 연결선
인접 (Adjacent)	간선으로 직접 연결된 노드
차수 (Degree)	한 노드에 연결된 간선의 수
진입차수 (Indegree)	나를 가리키는 간선의 수 (방향 그래프)
진출차수 (Outdegree)	내가 가리키는 간선의 수 (방향 그래프)
사이클 (Cycle)	시작 노드로 다시 돌아오는 경로
DAG	사이클 없는 방향 그래프 (위상정렬의 전제 조건)

---

7. 시간복잡도

표현 방법	DFS/BFS 시간복잡도
인접 리스트	O(V + E)
인접 행렬	O(V²)

V = 정점 수, E = 간선 수