그래프O(V + E)

DFS·BFS 완전탐색

연결된 걸 전부 훑어요. 스택이면 DFS, 큐면 BFS, 방문 체크만 잊지 마세요.

이럴 때 써요

연결된 노드를 하나도 빠짐없이 훑어야 할 때
연결 요소나 섬이 몇 덩어리인지 셀 때
격자(2D)에서 상하좌우로 퍼지며 영역을 채울 때
가중치가 없는 그래프에서 최단 거리(칸 수)를 구할 때

개념

그래프는 보통 인접 리스트로 들고 다녀요. graph[u]에 u와 이어진 이웃들을 담아 두면, u에서 갈 수 있는 곳을 바로 훑을 수 있어요. 훑을 땐 visited 배열로 한 번 다녀온 노드를 표시해서 다시 안 들어가게 막아요. 이게 없으면 사이클을 만나 무한히 뱅뱅 돌아요.DFS와 BFS는 다음에 어디를 볼지 고르는 방식만 달라요. DFS는 스택(또는 재귀)이라 한 갈래를 끝까지 파고들었다가 되돌아오고, BFS는 큐라 가까운 것부터 물결처럼 퍼져요. 그래서 BFS는 가중치 없는 그래프에서 최단 거리를 공짜로 줘요 — 먼저 도착한 게 가장 짧은 길이거든요.

	DFS	BFS
담는 곳	스택 / 재귀	큐(`queue`)
퍼지는 모양	한 갈래 끝까지	가까운 곳부터
잘 맞는 문제	연결 요소·경로 존재	최단 거리(칸 수)

격자 문제는 사실 그래프예요. 각 칸이 노드고, 상하좌우 네 칸이 이웃이에요. dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1] 처럼 방향 배열을 두고 네 방향을 돌면, 인접 리스트를 안 만들어도 이웃을 바로 구할 수 있어요.

"섬 개수 세기" — 1인 칸들이 몇 덩어리인지
grid =
  1 1 0
  0 1 0
  0 0 1
안 밟은 1을 만날 때마다 count++ 하고, 거기서 전부 물들여요
(0,0)=1  → 새 섬! count=1, BFS로 (0,1),(1,1) 까지 다 방문
(0,2)=0  → 물, 건너뛰기
(2,2)=1  → 새 섬! count=2, 이웃에 1 없음, 혼자
→ 섬 2개

패턴 코드

BFS로 최단 거리 (큐)방문 표시는 큐에 넣을 때 찍어요. JS는 shift()가 느려서 인덱스 포인터로 큐를 흉내 내고, Python은 deque를 써요.

javascript
Copy code
function bfs(graph, start) {
  const dist = new Array(graph.length).fill(-1);
  dist[start] = 0;
  const queue = [start];
  let head = 0; // shift 대신 인덱스 포인터
  while (head < queue.length) {
    const u = queue[head++];
    for (const v of graph[u]) {
      if (dist[v] !== -1) continue; // 이미 방문
      dist[v] = dist[u] + 1; // 넣을 때 거리 확정 = 방문 표시
      queue.push(v);
    }
  }
  return dist; // 못 닿은 곳은 -1
}

격자에서 섬 개수 세기 (BFS 물들이기)안 밟은 1을 만날 때마다 새 섬이에요. 거기서 이어진 1을 전부 방문 처리해 한 덩어리를 지워요.

javascript
Copy code
function countIslands(grid) {
  const R = grid.length, C = grid[0].length;
  const seen = Array.from({ length: R }, () => new Array(C).fill(false));
  const dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1];
  let count = 0;
  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      if (grid[i][j] !== 1 || seen[i][j]) continue;
      count++; // 새 섬 발견
      const queue = [[i, j]];
      let head = 0;
      seen[i][j] = true;
      while (head < queue.length) {
        const [x, y] = queue[head++];
        for (let d = 0; d < 4; d++) {
          const nx = x + dx[d], ny = y + dy[d];
          if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // 범위 밖
          if (grid[nx][ny] !== 1 || seen[nx][ny]) continue;
          seen[nx][ny] = true; // 넣을 때 방문 표시
          queue.push([nx, ny]);
        }
      }
    }
  }
  return count;
}

이 유형으로 풀어보기

← 슬라이딩 윈도우 다익스트라 최단경로 →