문제 개요
이 문제에서는 인접 리스트(adjacency list)로 표현된 방향 그래프가 주어집니다. 우리의 과제는 BFS(너비 우선 탐색)를 사용하여 하나의 시작 정점에서 그래프의 나머지 모든 정점까지의 경로를 찾는 프로그램을 작성하는 것입니다.
BFS(Breadth First Search, 너비 우선 탐색)는 그래프를 너비 방향으로 순회하는 알고리즘입니다. 탐색 도중 막다른 길(dead end)에 도달하면, 큐(queue)를 사용하여 다음에 탐색을 시작할 정점을 기억해 둡니다.
예제로 문제 이해하기
입력 −
아래와 같은 그래프가 주어졌다고 가정합니다.
출력
S A <= S B <= A <= S C <= S D <= C <= S
해결 접근 방법
이 문제를 해결하기 위해 그래프의 각 요소에 대해 BFS 탐색 알고리즘을 수행합니다. 이를 위해 방문 여부를 관리할 큐를 생성하고, visited(방문) 배열을 사용하여 해당 정점이 이미 방문되었는지 여부를 확인합니다(0과 1의 이진 값으로 방문 상태를 표시).
이제 예제를 단계별로 풀어보며 솔루션의 동작 원리를 살펴보겠습니다.
시작 정점 S에서 출발할 때,
정점 A는 S에서 직접 방문할 수 있습니다.
정점 B에 도달하려면 먼저 정점 A를 거쳐간 후 A를 통해 B에 도달합니다.
정점 C는 S에서 직접 방문할 수 있습니다.
정점 D에 도달하려면 먼저 정점 C를 방문한 후 D로 이동합니다.
구현 예제
다음은 위 솔루션의 동작을 보여주는 C++ 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
void printPath(vector<int> parent, int initial, int node){
while (initial != node){
cout<<node<<" <= ";
node = parent[node];
}
cout<<node<<endl;
}
void findPathBFS(vector<vector<int> > graphAdjList, int initial, int graphSize){
vector<int> parent(graphSize, 0);
vector<int> queue(graphSize, 0);
int front = -1, rear = -1;
vector<int> isVisited(graphSize, 0);
isVisited[0] = 1;
parent[0] = initial;
queue[++rear] = initial;
int k;
while (front != rear)
{
k = queue[++front];
for (int j:graphAdjList[k]){
if (isVisited[j] == 0){
queue[++rear] = j;
isVisited[j] = 1;
parent[j] = k;
}
}
}
for (k = 0; k < graphSize; k++)
printPath(parent, initial, k);
}
int main(){
vector<vector<int> > graphAdjList;
graphAdjList.push_back({1, 3});
graphAdjList.push_back({0, 2});
graphAdjList.push_back({1});
graphAdjList.push_back({4});
graphAdjList.push_back({0});
int graphSize = graphAdjList.size();
int initial = 0;
cout<<"The Path from vertex '0' to all other vertex in the graph is : \n";
findPathBFS(graphAdjList, initial, graphSize);
}실행 결과
The Path from vertex '0' to all other vertex in the graph is : 0 1 <= 0 2 <= 1 <= 0 3 <= 0 4 <= 3 <= 0
코드 설명
printPath 함수: parent 배열을 따라 거슬러 올라가면서 시작 정점부터 목표 정점까지의 경로를 출력합니다.
findPathBFS 함수: 큐를 직접 구현하여 BFS를 수행하고, 각 정점의 부모(parent) 정보를 기록합니다. 새로운 정점을 방문할 때마다 현재 정점을 부모로 저장하여 최단 경로를 역추적할 수 있게 합니다.
main 함수: 인접 리스트 형태로 그래프를 구성한 뒤, 정점 0에서 출발하는 BFS를 실행하여 모든 정점까지의 경로를 출력합니다.
BFS의 시간 복잡도는 O(V + E)이며, 여기서 V는 정점의 수, E는 간선의 수입니다. 이 알고리즘은 가중치가 없는 그래프에서 시작 정점으로부터 각 정점까지의 최단 경로를 보장한다는 장점이 있습니다.