커리큘럼/페이즈 3 · 자료구조와 그래프
15주차

그래프와 DFS · BFS

트리의 제약을 풀면 그래프예요. 대신 방문 표시가 필요해져요.

개념

그래프는 정점과 간선으로 이루어져요. 트리도 그래프의 일종인데, 사이클이 없고 부모가 하나뿐이라는 제약이 붙은 특수한 경우예요. 그 제약을 풀면 같은 곳을 다시 방문할 수 있게 되고, 그래서 그래프 탐색에는 방문 배열이 꼭 필요해요.

그래프를 코드로 표현하기

표현메모리간선 확인이웃 순회언제
인접 리스트O(V + E)O(차수)빠름대부분의 경우
인접 행렬O(V²)O(1)O(V)정점이 적고 간선이 빽빽할 때
정점이 10만 개면 인접 행렬은 100억 칸이라 아예 만들 수 없어요. 특별한 이유가 없으면 인접 리스트를 써요. 격자(지도) 문제는 아예 자료구조를 만들지 않고, 좌표 자체를 정점으로 보고 상하좌우를 간선으로 취급해요.

DFS와 BFS

미로에서 길을 찾는 두 가지 성격이라고 생각하면 쉬워요. DFS는 한 방향으로 끝까지 가 보는 사람이에요. 막히면 갈림길로 되돌아와 다음 길을 시도해요(재귀·스택). BFS는 연못에 던진 물결이에요. 시작점에서 한 칸, 두 칸, 세 칸씩 동심원으로 퍼져요(큐). 둘 다 모든 정점을 빠짐없이 훑고, 차이는 다음에 어디를 볼 것인가뿐이에요.
  • DFS — 경로를 따라가야 할 때, 연결 여부만 볼 때, 재귀로 짧게 쓰고 싶을 때
  • BFS — 최단 거리가 필요할 때. 물결이 처음 닿는 순간이 곧 최단 거리라, 간선 가중치가 모두 같으면 BFS가 곧 최단 경로예요 (16주차)
같은 그래프를 두 방식으로 훑으면 방문 순서가 어떻게 갈리는지 직접 따라가 볼게요. 이웃은 번호가 작은 쪽부터 본다고 할게요.
정점 0에서 출발 — BFS는 층층이, DFS는 깊이
그래프 (양방향)          이웃 목록
      0                 0 : 1, 2
     / \                1 : 0, 3
    1   2               2 : 0, 4
    |   |               3 : 1, 4
    3 - 4               4 : 2, 3
​
BFS(0) — 큐로 가까운 곳부터
  거리 0 :  0
  거리 1 :  1  2      (0의 이웃)
  거리 2 :  3  4      (1·2의 이웃)
  방문 순서 → 0 1 2 3 4
​
DFS(0) — 갈 수 있는 데까지 파고들기
  0 → 1 → 3 → 4 → 2     (4에서 막히자 2로)
  방문 순서 → 0 1 3 4 2

패턴 코드

인접 리스트 만들기
javascript
const graph = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
  graph[a].push(b);
  graph[b].push(a); // 방향 그래프면 이 줄을 뺍니다
}
DFS (재귀)
javascript
const visited = new Array(n).fill(false);
function dfs(v) {
  visited[v] = true;
  for (const next of graph[v]) {
    if (!visited[next]) dfs(next);
  }
}
BFS (큐)방문 표시를 큐에 넣을 때 하는 게 핵심이에요.
javascript
const visited = new Array(n).fill(false);
const queue = [start];
let head = 0;
visited[start] = true;
while (head < queue.length) {
  const v = queue[head++];
  for (const next of graph[v]) {
    if (visited[next]) continue;
    visited[next] = true;
    queue.push(next);
  }
}
격자에서 상하좌우 훑기4주차에서 만든 델타 배열과 같은 도구예요. 격자 문제마다 나와요.
javascript
const DX = [-1, 1, 0, 0];
const DY = [0, 0, -1, 1];
for (let d = 0; d < 4; d++) {
  const nx = x + DX[d];
  const ny = y + DY[d];
  if (nx < 0 || ny < 0 || nx >= rows || ny >= cols) continue;
  // ...
}

이번 주 문제

이번 주 진행0 / 4
주차 진행률
이번 주 주제로 골라둔 문제예요. 채점은 프로그래머스에서 하고, 풀고 나면 여기에 체크해 두세요. 난이도 순으로 보여줘요.
프로그래머스 진행률
  • 타겟 넘버
    Lv. 2풀기
  • 네트워크
    Lv. 3풀기
  • 단어 변환
    Lv. 3풀기
  • 여행경로
    Lv. 3풀기

셀프 체크

다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.
  1. 인접 행렬이 불리해지는 조건은 무엇인가요?
  2. BFS에서 방문 표시를 꺼낼 때 하면 구체적으로 무슨 일이 벌어지나요?
  3. DFS와 BFS 중 무엇을 고를지 어떤 기준으로 판단하나요?
← 14주차 · 트리와 이진 트리16주차 · BFS 최단 거리와 격자 탐색 →