정보처리기사 너비 우선 탐색(BFS) 완벽 정리 — 큐로 그래프 운행법 기출 정복

BFS, 그림으로 보면 알 것 같은데 막상 문제에서 막히는 이유

정보처리기사 필기 시험에서 너비 우선 탐색(BFS, Breadth-First Search)은 그래프 운행법 파트의 단골 출제 유형입니다. 개념은 이해했는데 노드 번호 순서로 방문하는 기준이나 큐(Queue)에 노드가 중복으로 쌓이는 상황에서 헷갈려 틀리는 경우가 많습니다. BFS는 직접 큐 상태를 손으로 따라 그리지 않으면 실수가 생기기 쉬운 유형입니다.

이 강의는 큐(Queue)를 활용한 선입선출 탐색 원리를 중심으로, 시험지 한편에 큐를 직접 그리며 따라오는 방식으로 BFS를 완전히 체득할 수 있도록 구성했습니다.

BFS란 무엇인가 — 큐로 레벨 단위로 넓게 퍼지는 원리

너비 우선 탐색은 이름 그대로 출발 노드에서 가까운 노드부터 한 단계(레벨)씩 순서대로 넓게 퍼지며 방문하는 탐색 방법입니다. 깊이 우선 탐색(DFS)이 한 방향으로 끝까지 파고든 뒤 되돌아오는 것과 달리, BFS는 "지금 볼 수 있는 이웃을 전부 줄 세워 놓고, 줄의 맨 앞부터 순서대로 처리"하는 방식으로 동작합니다. 이 "줄 세우기"를 담당하는 자료구조가 바로 큐(Queue)이며, 큐는 먼저 들어간 데이터가 먼저 나오는 선입선출(FIFO, First-In First-Out) 구조입니다.

DFS와 BFS의 차이를 자료구조 관점에서 정리하면 다음과 같습니다.

구분	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
사용 자료구조	큐(Queue) — 선입선출(FIFO)	스택(재귀 호출 스택 포함) — 후입선출(LIFO)
진행 방식	가까운 노드부터 한 단계씩 넓게 퍼짐	한 갈래로 끝까지 파고든 뒤 되돌아옴
대표 활용	최단 경로(가중치 없는 그래프), 레벨별 탐색	백트래킹, 경로 존재 여부 판단, 위상 정렬
기억법	"넓게 먼저" — 가까운 곳부터 훑는다	"깊게 먼저" — 갈 수 있는 데까지 간다

핵심 규칙은 두 가지입니다.

1. 노드를 큐에 넣는 순간(인큐 시점) 즉시 "방문 예정" 표시를 한다. (같은 노드가 큐에 중복으로 들어가지 않도록)
2. 큐의 맨 앞에서 노드를 하나 꺼내(디큐) 처리하고, 그 노드의 미방문 이웃을 오름차순으로 모두 큐 뒤에 추가한다.

이 두 규칙, 특히 "방문 표시는 꺼낼 때가 아니라 넣을 때 한다"는 원칙을 지키지 않으면 시험에서 아주 흔한 실수가 발생합니다. 이 부분은 아래 실전 추적과 함정 파트에서 직접 확인해 보겠습니다.

같은 그래프, DFS는 이렇게 갔었죠? — 이번엔 BFS로 추적합니다

누구나패스의 정보처리기사 DFS 완전 정복 글에서 다룬 것과 동일한 무방향 그래프로 BFS를 추적해 보겠습니다. DFS 이론은 그 글에서 이미 자세히 설명했으니 여기서는 반복하지 않고, "이 그래프에서 DFS는 1 → 2 → 4 → 3 → 5 순서로 갔었죠?"라는 것만 기억한 채, BFS는 같은 그래프에서 과연 어떤 순서로 방문하는지 비교하며 살펴보겠습니다.

간선 목록: 1-2, 1-3, 2-4, 3-4, 4-5

인접 리스트(오름차순 방문 규칙)는 다음과 같습니다.

노드	인접 노드(오름차순)
1	2, 3
2	1, 4
3	1, 4
4	2, 3, 5
5	4

BFS 방문 순서 직접 추적하기 (큐 상태 변화 표)

출발 노드 1을 큐에 넣으면서 동시에 "방문 예정" 표시를 하고 시작합니다. 아래 표에서 "처리 전 큐"는 해당 단계에서 노드를 꺼내기 직전의 큐 상태, "처리 후 큐"는 이웃을 모두 큐에 추가한 뒤의 상태입니다.

단계	처리 전 큐	꺼낸 노드(디큐)	이웃 확인 및 처리	처리 후 큐	방문 순서 누적
시작	-	-	1을 큐에 넣고 방문 표시	[1]	-
1	[1]	1	이웃 2, 3 모두 미방문 → 둘 다 방문 표시 후 큐에 추가	[2, 3]	1
2	[2, 3]	2	이웃 1(방문됨, 건너뜀), 4(미방문) → 4 방문 표시 후 추가	[3, 4]	1, 2
3	[3, 4]	3	이웃 1(방문됨), 4(이미 방문 표시됨 → 중복 추가하지 않고 건너뜀)	[4]	1, 2, 3
4	[4]	4	이웃 2(방문됨), 3(방문됨), 5(미방문) → 5 방문 표시 후 추가	[5]	1, 2, 3, 4
5	[5]	5	이웃 4(방문됨) → 추가할 노드 없음	[]	1, 2, 3, 4, 5

큐가 완전히 비면 탐색이 끝납니다. 최종 BFS 방문 순서는 1 → 2 → 3 → 4 → 5입니다. 5개 노드가 정확히 한 번씩만 등장했는지 세어보면 검산이 끝납니다(1, 2, 3, 4, 5 — 총 5개, 중복 없음 확인).

주목할 지점은 3단계입니다. 노드 3을 처리할 때 이웃 4를 확인하는데, 4는 이미 2단계에서 방문 표시가 되어 큐에 들어가 있는 상태입니다. 만약 이때 "이미 큐에 있는지"를 확인하지 않고 무조건 다시 추가했다면 큐는 [4, 4]처럼 같은 노드가 중복으로 쌓이는 상태가 됩니다. 이 부분이 BFS 문제에서 가장 흔하게 실수가 나오는 지점이므로, 다음 파트에서 왜 이런 일이 생기고 어떻게 막는지 정확히 짚어보겠습니다.

시험 함정: 방문 표시를 "언제" 하느냐가 큐 중복을 좌우한다

많은 수험생이 DFS의 "도착 즉시 방문 표시" 습관을 BFS에도 그대로 적용해서, 노드를 큐에서 꺼낼 때(디큐 시점)에만 방문 표시를 합니다. 이 방식대로 위 그래프를 다시 추적하면 어떻게 되는지 보겠습니다.

단계	처리 전 큐	꺼낸 노드	문제가 되는 지점	처리 후 큐
1	[1]	1	방문 표시(디큐 시점) 후 이웃 2, 3을 조건 없이 추가	[2, 3]
2	[2, 3]	2	방문 표시 후 이웃 4를 (아직 방문 표시 안 됨) 추가	[3, 4]
3	[3, 4]	3	방문 표시 후 이웃 4를 확인 — 4는 아직 "방문 표시"가 안 된 상태(큐에만 있음)이므로 또 추가됨	[4, 4] ← 중복 발생

이렇게 되면 노드 4가 큐에 두 번 들어가고, 이후 4를 두 번 꺼내 처리하면서 방문 순서에 4가 중복 기록되거나, 이를 막기 위한 추가 예외 처리가 필요해집니다. 결론적으로 BFS에서는 "방문 표시를 큐에 넣는 순간(인큐 시점)"에 해야 이런 중복을 원천적으로 막을 수 있습니다. 이것이 BFS 코드에서 visited 체크를 디큐 직후가 아니라 인큐 직전에 하는 이유이며, 정보처리기사 시험에서도 "큐에 중복으로 들어간 노드를 어떻게 처리하는가"를 묻는 문제가 종종 출제됩니다.

DFS와 BFS, 같은 그래프에서 이렇게 다릅니다

동일한 그래프, 동일한 "번호가 작은 순서로 방문" 규칙을 적용했는데도 두 탐색법의 결과는 다릅니다.

구분	방문 순서	진행 특징
DFS (자매글 보기)	1 → 2 → 4 → 3 → 5	2에서 바로 4로 파고든 뒤, 더 갈 곳이 없을 때 3, 5를 백트래킹으로 처리
BFS (이 글)	1 → 2 → 3 → 4 → 5	1의 이웃 2, 3을 먼저 모두 방문한 뒤에야 다음 레벨인 4로 이동

두 결과는 1 → 2까지는 완전히 동일합니다. 갈라지는 지점은 세 번째 방문 노드입니다. DFS는 2에서 곧바로 이웃 4로 더 깊이 파고들지만, BFS는 "1의 이웃을 전부 처리하고 나서야 다음 단계로 넘어간다"는 원칙에 따라 아직 큐에 남아있던 3을 먼저 처리합니다. "같은 레벨을 다 비우고 나서 다음 레벨로 간다"는 이 성질이 BFS를 BFS답게 만드는 핵심이며, 다음 파트에서 다룰 최단 경로 보장의 근거이기도 합니다.

최단 경로 탐색에 BFS가 유리한 이유

BFS는 출발 노드로부터 가까운 노드(적은 간선 수)부터 순서대로 방문하기 때문에, 가중치가 없는 그래프에서는 어떤 노드가 처음 큐에 들어간 시점 = 그 노드까지의 최단 경로(최소 간선 수)가 항상 보장됩니다. 위 추적 표에서 각 노드가 몇 번째 단계에서 큐에 들어갔는지를 "출발점으로부터의 거리(레벨)"로 정리하면 다음과 같습니다.

노드	1로부터의 최단 거리(간선 수)	도달 경로 예시
1	0	출발점
2	1	1 → 2
3	1	1 → 3
4	2	1 → 2 → 4 (또는 1 → 3 → 4)
5	3	1 → 2 → 4 → 5 (또는 1 → 3 → 4 → 5)

이 표에서 거리 값이 0, 1, 1, 2, 3으로 절대 감소하지 않고 단계마다 증가하거나 유지되는 것을 볼 수 있습니다. 이것이 BFS가 "레벨 단위로 넓게 퍼진다"고 표현되는 이유입니다. 반면 DFS는 한 방향으로 먼저 깊이 들어가는 특성상, 노드를 처음 방문하는 순서가 실제 최단 거리와 무관하게 뒤섞일 수 있습니다. 예를 들어 그래프의 형태에 따라서는 DFS가 우회 경로를 먼저 파고들어 실제로는 더 먼 노드를 더 가까운 노드보다 먼저 방문하는 경우도 얼마든지 생깁니다. 그래서 "두 노드 사이의 최단 경로(간선 수)를 구하라"는 유형의 문제는 거의 예외 없이 BFS로 풀어야 하며, 이는 정보처리기사 시험에서 BFS의 활용처를 묻는 문제의 정답 근거로 자주 등장합니다. (단, 간선마다 가중치가 다른 그래프의 최단 경로는 BFS가 아니라 다익스트라 알고리즘 등 별도의 방법이 필요합니다.)

큐 기반 BFS 코드로 검증하기

손으로 추적한 결과가 맞는지, 위 그래프를 그대로 코드로 옮겨 큐 기반 BFS를 돌려보면 검증할 수 있습니다.

const graph = {
  1: [2, 3],
  2: [1, 4],
  3: [1, 4],
  4: [2, 3, 5],
  5: [4],
};

function bfs(start) {
  const visited = new Set([start]); // 규칙 1: 큐에 넣는 순간(여기서는 시작 노드) 즉시 방문 표시
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift();     // 큐의 맨 앞에서 꺼낸다 (FIFO)
    order.push(node);

    for (const next of graph[node]) {
      if (!visited.has(next)) {
        visited.add(next);          // 규칙 1: 인큐 직전에 방문 표시 → 중복 인큐 방지
        queue.push(next);           // 규칙 2: 큐 뒤에 추가
      }
    }
  }
  return order;
}

console.log(bfs(1)); // [1, 2, 3, 4, 5]

손으로 추적한 1 → 2 → 3 → 4 → 5와 코드 실행 결과가 정확히 일치합니다. 이 코드에서 visited.add(next)가 queue.push(next)보다 먼저, 즉 인큐 직전에 실행된다는 점이 핵심입니다. 이 순서를 node를 꺼낸 직후로 옮기면(디큐 시점 마킹) 앞서 함정 파트에서 살펴본 것처럼 큐에 같은 노드가 중복으로 쌓일 수 있습니다.

시험에서 자주 나오는 함정

• 스택과 큐를 혼동한다 — DFS 문제 풀이 습관이 남아 BFS 문제에서도 나중에 넣은 노드를 먼저 꺼내는 실수를 합니다. BFS는 반드시 먼저 넣은 노드가 먼저 나오는 큐(FIFO)를 사용합니다.
• 방문 표시 시점을 디큐 시점으로 착각한다 — 위에서 확인했듯, 방문 표시를 꺼낼 때 하면 같은 노드가 큐에 중복으로 들어갈 수 있습니다. BFS는 인큐 시점에 방문 표시를 하는 것이 표준입니다.
• 이웃 노드 방문 순서 규칙을 놓친다 — "번호가 작은 순서로", "알파벳 순서로" 등 문제에 명시된 규칙을 무시하고 아무 순서로나 큐에 넣으면 답이 달라집니다. 규칙을 먼저 확인하세요.
• 레벨(거리) 개념과 방문 순서를 혼동한다 — 같은 레벨(거리)에 있는 노드가 여러 개면, 그 안에서의 순서는 방문 규칙(번호·알파벳 순)에 따라 정해집니다. "거리가 같으면 무조건 동시 방문"이라고 착각하지 않아야 합니다.
• DFS 결과와 BFS 결과를 뒤섞어 적는다 — 이번 글의 그래프처럼 1, 2까지는 같아도 세 번째 노드부터 갈라지는 경우가 많습니다. 문제가 어떤 탐색을 요구하는지 문두를 다시 확인하는 습관이 필요합니다.

이런 분께 딱 맞는 강의입니다

• 정보처리기사 필기를 준비 중인 수험생
• BFS 개념은 알지만 큐 상태를 추적하다 중간에 꼬여서 자꾸 틀리는 분
• DFS와 BFS의 차이, 특히 같은 그래프에서 결과가 왜 다른지 헷갈리는 분
• 최단 경로 문제에서 왜 BFS를 써야 하는지 정확히 이해하고 싶은 분
• 자료구조·알고리즘이 낯선 비전공자 수험생

수강 정보

항목	내용
수강료	무료
강의 수	1강
카테고리	자격증
강사	누구나패스
수강 방식	온라인(PC·모바일)

회원가입 후 즉시 수강할 수 있으며, 언제든 반복해서 볼 수 있습니다. 추가 비용 없이 무료로 제공됩니다.

자주 묻는 질문

Q. DFS 글이랑 같은 그래프인데 왜 방문 순서가 다른가요?

탐색 전략 자체가 다르기 때문입니다. DFS는 한 방향으로 갈 수 있는 데까지 파고드는 반면, BFS는 가까운 노드부터 레벨 단위로 넓게 퍼집니다. 이 글의 그래프에서는 1 → 2까지는 같지만, DFS는 다음으로 4를 방문(1→2→4→3→5)하고 BFS는 같은 레벨의 3을 먼저 방문(1→2→3→4→5)한다는 차이가 있습니다.

Q. 큐를 직접 그리지 않고도 시험에서 빠르게 풀 수 있나요?

네. 강의에서는 큐 칸을 매번 다시 그리는 대신, 이 글의 표처럼 "처리 전 큐 → 꺼낸 노드 → 처리 후 큐"를 한 줄씩 이어가는 방식으로 빠르게 답을 적어내는 방법을 안내합니다.

Q. 최단 경로 문제는 항상 BFS로 풀어야 하나요?

모든 간선의 가중치가 같거나(또는 가중치가 없는) 그래프라면 BFS로 최단 경로(최소 간선 수)를 구할 수 있습니다. 다만 간선마다 비용이 다른 그래프의 최단 경로는 다익스트라 알고리즘 등 다른 방법이 필요하며, 이 부분은 정보처리기사 시험에서도 구분해서 물어보는 포인트입니다.

Q. 정처기 관련 다른 강의도 있나요?

누구나패스에서 DFS, 정렬 알고리즘, 서브넷 마스크, 수식 표기법 등 필기 시리즈를 무료로 제공합니다. 무료 강의 목록에서 확인하세요.

지금 바로 무료로 확인하세요

BFS는 "방문 표시를 언제 하는가"만 정확히 지키면 큐 중복 없이 반드시 맞힐 수 있는 유형입니다. DFS 완전 정복 글과 함께 보면 같은 그래프에서 두 탐색법이 어떻게 다르게 움직이는지 확실히 비교할 수 있습니다. 이 강의로 너비 우선 탐색을 완전히 체득하고 그래프 운행법 파트를 자신 있게 마무리하세요.

강의 자세히 보기 →