그래프 탐색: BFS·DFS

그래프 표현

인접 리스트가 일반적입니다.

const g = Array.from({ length: n }, () => []);
g[u].append?.(v); // python
g[u].push(v);

격자(미로)는 4방향 이동으로 암묵적 그래프입니다.

DFS

깊이 우선. 재귀 또는 명시 스택.

• 연결 요소
• 경로 존재
• 위상·사이클 검출의 기초

깊은 재귀는 브라우저에서 위험 → 스택으로 바꾸기.

BFS

큐로 넓이 우선.

• 가중치 없는 최단 간선 수
• 레벨 단위 처리

const q = [start];
const dist = Array(n).fill(-1);
dist[start] = 0;
while (q.length) {
  const u = q.shift();
  for (const v of g[u]) {
    if (dist[v] === -1) {
      dist[v] = dist[u] + 1;
      q.push(v);
    }
  }
}

shift는 O(n)이라 큰 n에서는 인덱스 큐가 낫습니다.

방문 배열

같은 노드를 두 번 넣지 않도록 visited / dist !== -1로 막습니다.
안 막으면 무한 루프·메모리 폭주.

격자 섬 세기

육지를 만나면 DFS/BFS로 연결된 육지를 전부 방문 처리 → 섬 +1.
이 사이트 island 태그 문제와 연결됩니다.

복잡도

정점 V, 간선 E일 때 BFS/DFS는 O(V+E).
격자 n×m이면 O(nm).

큐 구현 팁 (JS)

let head = 0;
const q = [start];
while (head < q.length) {
  const u = q[head++];
  ...
}

shift() 대신 인덱스를 올리면 큰 입력에서 낫습니다.

연습

섬의 개수·미로 도달 가능 여부 문제를 island/bfs 태그로 찾아 보세요.