Data Structure / Algorithm - BFS와 최단 경로
BFS의 동작 원리
BFS는 그래프의 노드를 탐색하는 또 다른 방법으로, 시작 노드에 인접한 노드를 먼저 탐색하는 방식이다.
이 알고리즘은 주로 큐(Queue)를 사용하여 구현되며, 다음과 같은 순서로 실행된다.
- 시작 노드 선택 및 큐에 삽입 : 탐색을 시작할 노드를 선택하고, 이 노드를 큐에 삽입
- 큐에서 노드 제거 및 방문 : 큐에서 노드를 하나 제거하고, 해당 노드를 방문 및 방문처리
- 인접 노드 큐에 삽입 : 방문한 노드와 인접한 모든 노드를 큐에 삽입
- 반복 실행 : 큐가 비어있을 때까지 2번과 3번의 과정을 반복
BFS의 LEVEL
BFS의 장단점
BFS는 레벨(Level) 별로 탐색하므로, 최단 경로 문제에 자주 사용된다.
또한, DFS에 비해 구현이 조금 더 간단하며, 재귀 호출을 사용하지 않기 때문에 스택 오버플로의 위험이 적다.
하지만 BFS는 탐색 과정에서 큐에 모든 인접 노드를 저장하기 때문에,
특히 그래프가 밀집되어 있거나 노드 수가 많은 경우, 큐에 많은 노드가 저장되어 상당한 양의 메모리를 사용할 수 있다.
백준 1697번 - 숨바꼭질
문제 설명
이 문제에서 BFS를 이용해야 하는 이유
수빈이의 위치가 주어졌을 때 동생에게 가기 위한 경로가 무수히 많다.
그리고 한 위치에서 수빈이가 움직일 수 있는 경우는 다음과 같다.
수빈이의 이동 경우의 수. LEVEL은 시간을 의미한다
- 왼쪽으로 걷기
- 오른쪽으로 걷기
- 순간이동
하지만 ‘최단 시간’으로 가야 하므로 각 상황에서 선택할 수 있는 경로인 '너비'를 우선으로 탐색해야 한다.
수빈이가 동생을 찾았을 때의 LEVEL(경과 시간)이 최단 경로인 것이므로 BFS로 풀어야 한다고 생각했다.
풀이 방법
int N; cin >> N; // 수빈이의 위치
int K; cin >> K; // 동생의 위치
const int result = BFS(N, K);
cout << result << '\n';
BFS의 매개변수로 수빈이의 시작 위치와 수빈이가 도착해야 하는 목적지인 동생의 위치를 넣어준다.
BFS의 return이 정답(최단 시간)을 반환하도록 함수를 설계할 것이다.
// 걷기 기능
int Walk(int x, int dir)
{
// X-1 또는 X+1로 이동하게 된다
x += dir;
return x;
}
// 순간이동 기능
int Teleport(int x)
{
// 2*X의 위치로 이동하게 된다
// *무조건 오른쪽으로만 이동*
x *= 2;
return x;
}
우선, 수빈이의 이동에 대한 기능을 구현한다.
int BFS(int subinPos, int sisterPos)
{
// BFS를 위한 준비 단계
std::queue<std::pair<int, int>> myQueue; // 1. 큐 생성 <수빈의 위치, 이동 시간>
bool visited[100001] = { false, }; // 2. 방문 여부를 저장할 배열 생성
// 초기화
myQueue.push(std::make_pair(subinPos, 0));
visited[subinPos] = true;
// 수빈이의 위치와 경과 시간에 대한 정보가 큐에 1개 들어가 있는 상태로 BFS 시작
// 인접한 노드에 접근하며 방문 여부를 체크하고, 방문하지 않은 노드라면 큐에 넣는다.
while (!myQueue.empty())
{
// 큐의 맨 앞에 있는 정보를 가져온 후 큐에서 제거
auto prevInfo = myQueue.front();
myQueue.pop();
// 목표 지점에 도달했다면 걸린 시간을 리턴
if (prevInfo.first == sisterPos)
return prevInfo.second;
// 3가지 이동 상황을 계산
// 1. 오른쪽으로 걷기
int rightResult = Walk(prevInfo.first, 1);
// 길을 벗어났는지 체크
if (rightResult <= 100000 && rightResult >= 0)
{
// 방문하지 않은 노드라면 큐에 넣는다.
if (!visited[rightResult])
{
// 큐에 넣을 때, 수빈이의 위치를 업데이트 및 이동 시간을 1 증가시킨다.
myQueue.push(std::make_pair(rightResult, prevInfo.second + 1));
// 방문 처리
visited[rightResult] = true;
}
}
// 2. 왼쪽으로 걷기
int leftResult = Walk(prevInfo.first, -1);
if (leftResult <= 100000 && leftResult >= 0)
{
if (!visited[leftResult])
{
myQueue.push(std::make_pair(leftResult, prevInfo.second + 1));
visited[leftResult] = true;
}
}
// 3. 순간이동
int teleportResult = Teleport(prevInfo.first);
if (teleportResult <= 100000 && teleportResult >= 0)
{
if (!visited[teleportResult])
{
myQueue.push(std::make_pair(teleportResult, prevInfo.second + 1));
visited[teleportResult] = true;
}
}
}
return 0;
}
수빈이가 최단 경로를 찾아가는 기능을, BFS를 이용해서 구현한다.
댓글남기기