[코드트리] BFS 알고리즘 쉽게 이해하기 (개념부터 구현까지 총정리)

https://www.codetree.ai/ko/no-free-lunch-2026

3년 만에 돌아온, 코드트리 청약 통장 챌린지 | 코드트리

 

개인적으로 삼성 코테에서 BFS보다 더 중요한 알고리즘은 없다고 생각이 든다. 그럼으로 BFS에 대한 복습을 해보도록 하겠다.

우선 나는 지금 코드트리의 커리큘럼을 따라가고 있고 현재 BFS챕터의 BFS탐색 문제들은 모두 푼 상태이고 지금은 "가중치가 동일한 그래프에서의 BFS" Lesson을 풀고 있는 상태이다. 

 

BFS는 Breadth-First Search의 약자로 한국어로 너비 우선 탐색을 뜻한다. 

핵심 알고리즘은 시작 노드에서부터 가장 가까운 인접 노드를 먼저 탐색하는 방식을 취하는 것이다. 

조금 빌려쓰겠습니다...

예를 들어 1번이 시작 노드라고 치자면 1을 먼저 방문하고 그 다음에 인접한 노드인 2, 3, 4 순서로 노드를 방문하게 된다.

그렇게 되면 방문 순서는 다음과 같이 된다. 1, 2, 3, 4, 5, 6, 7

 

사실 BFS알고리즘 경우는 너무 기본적인 알고리즘에 포함되다 보니 대충 알고리즘 정도는 이미 많이 알고 있을 것이다. 그러니 어떻게 구현할지를 보도록 하자.

 

이것도 좀 빌리겠습니다...

BFS를 구현할 때에는 2가지 방식이 있다. 첫번째는 배열로 구현하는 방식이다. 2차원 배열을 구성하여 서로 연결되어 있는 노드끼리는 1로 표시를 하고 그렇지 않은 관계는 0을 저장해서 그래프의 관계를 설명한 방식이다.

 

두번째 방식은 연결 리스트로 구현한 방식으로 하나의 노드에 연결된 모든 노드들을 리스트로 포인트한 방식이다. 근데 해당 방식은 사실 알고리즘 문제에 잘 안나타나고 추후에 그리드를 사용한 시뮬레이션 문제에 사용하기 적합하지 않은 관계로 정리하지 않겠다. 

 

암튼 그럼 첫번째 방식으로 BFS를 구현하면 다음과 같다.

void BFS() {
	while (!q.empty()) {
		pair<int, int> pos = q.front();
		q.pop();
		int cx = pos.first;
		int cy = pos.second;

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if (visited[nx][ny]) continue;

			visited[nx][ny] = true;
			q.push({ nx, ny });
		}
	}
}

 

사실 위 구현 상황은 완전히 그래프에 맞춘게 아니긴 한데 위와 같은 형식이 추후에 있을 문제에 더 많이 사용함으로 위 코드를 통해서 설명하겠다.

 

일단 q는 인접한 노드들을 저장하는데 사용한다. 맨 위 그래프 예시만 보아도 1과 인접한 노드는 2, 3, 4 이렇게 3가지 노드가 있었다. 각 노드들에 대한 BFS를 처리해야 함으로 우선 queue에 저장을 한다. 그리고 while반복문이 실행될 때마다 queue에서 한 노드씩 꺼내온다. 

위 코드는 grid에서 상하좌우로의 인접한 노드를 방문한 것이다. 대부분의 어렵지 않은 문제들은 2차원 그리드에서 현재 위치로부터 상하좌우로만 이동이 가능하다고 쓰여져있는데 난이도가 올라갈 수록 나이트처럼 움직이거나 대각선으로 움직이는 문제도 많이 출제가 되는데 그럴때는 dx, dy배열에 더 많은 이동 옵션들을 추가하면 된다.

어쨌든 이동 가능한 곳이라면 visited처리를 해주고 queue에 넣어주면서 반복문을 실행하면 된다.

 

요즘 내가 다니는 학교에서는 사실 AI가 너무 유행이다 보니까 직접 코딩을 안하는 학생들이 너무 많은 것 같다. 그래서 알고리즘은 아는데 AI로만 코딩을 해서 직접 구현하라고 했을 때에는 어려워하는 분이 많다. 세상이 너무 빨리 바뀌고 AI로 인해 많은 업무 또는 능력들이 저평가 취급 당하는데 사실 그렇지 않은 경우가 많은 것 같다. 뭐 일단 나는 지금 내가 재밌다고 생각하는 일들만 하고 있어서 코테도 재밌게 연습하고 있다.

 

암튼 BFS 정리였습니다, 다들 화이팅하세요.