6. BFS - 최단 경로 전략
bfs는 그래프의 최단 경로를 찾는 가장 유명한 방법이지만, 모든 최단 경로 문제를 bfs로 풀 수 있는 것은 아니다.
문제에 따라 bfs보다 더 효율적인 알고리즘이 존재하기도 한다.
예제 - 15-퍼즐
4*4 격자에 끼워진 열다섯개의 숫자 타일을 순서에 맞게 맞추는 퍼즐이다.
빈 칸에 상하좌우로 인접한 타일 중 하나를 빈칸으로 움직이기를 반복해,
주어진 상태를 숫자 타일을 오름차순으로 정렬한 상태로 만드는 것이 퍼즐의 목표인 것이다.
이 때 퍼즐을 해결하기 위한 최소의 움직임의 수를 구해보자.
우선 문제를 해결하기 위해 퍼즐의 각 상태를 정점으로 하는 그래프를 만들 수 있다.
현재 정점의 상태에서 빈칸에 인접한 타일 중 하나를 빈칸으로 옮겨서 만들 수 있는 상태 정점으로 간선을 연결한다.
이 때 간선은 양방향 간선이 된다.
이렇게 그래프를 모델링하면, 문제는 그래프 상에서 마지막 상태정점으로 가는 최단 경로의 길이를 구하는 문제가 된다.
너비 우선 탐색
우선 bfs를 통해 이 문제를 풀어보도록 하자.
각 퍼즐의 상태를 State 라는 객체로 나타내도록 하면,
각 정점의 방문 여부는 정수형 배열이 아니라 State형의 키를 가지는 map을 통해서 구현할 수 있다.
// 15-퍼즐 문제를 해결하기 위한 bfs 알고리즘
class State {
// 현재 상태에서 한번의 움직임으로 만들 수 있는 상태들의 목록을 리턴한다.
vector<State> getAdjacent() const;
}
typedef map<State, int> stateMap;
int bfs(State start, State finish){
// 시작 상태와 종료 상태가 같으면 0 리턴
if(start == finish) return 0;
stateMap c; // 시작 정점에서 각 정점까지 도달하는 최소 경로의 길이
queue<State> q;
c[start] = 0;
q.push(start);
while(!q.empty()){
State here = q.front();
q.pop();
int cost = c[here];
vector<State> adj = here.getAdjcent();
for(int i = 0; i < adj.size(); i++){
if(c.count(adj[i]) == 0){ // 아직까지 이 정점이 발견되지 않았다면
if(adj[i] == finish) return cost + 1; // 이 정점이 종료 정점이면 최소 경로 길이 리턴
q.push(adj[i]);
c[adj[i]] = cost + 1;
}
}
}
return -1;
}
위의 방법은 시작 정점에서 종료 정점까지의 길이에 따라 수행시간이 결정된다.
종료 정점이 가까이 위치한다면 함수는 금방 종료하겠지만, 경로의 길이가 길어질수록 그 수행시간은 매우 길어지게 된다.
각 정점 당 인접한 정점은 4개이고, 중복되는 경우를 제외하면 각 정점을 탐색할 때마다 대략 3개씩 늘어나게 되기 때문이다.
즉 경로의 길이가 증가함에 따라 수행시간은 지수적으로 증가하게 된다.
양방향 탐색
위와 같이 두 정점 사이의 최단 경로를 찾을 때 굉장히 간단하면서 유용하게 쓸 수 있는 알고리즘 중 하나가 양방향 탐색이다.
시작 정점에서 시작하는 정방향 탐색과 종료 정점에서 시작하는 역방향 탐색을 동시에 시작하면서,
이 둘이 가운데서 만나면 탐색을 종료하는 것이다.
이는 양쪽에서 bfs 를 실행하기 때문에 일반적인 bfs보다 탐색의 깊이가 반으로 줄어들게 된다.
따라서 탐색의 깊이가 깊어질수록 수행시간이 지수적으로 증가하게 되는 위의 문제같은 경우 사용하기 유용하다.
양방향 탐색을 구현하는 것은 어렵지 않다.
정방향 탐색과 역방향 탐색에서 방문할 정점들을 모두 같은 큐에 넣고 하나씩 방문하되,
정방향 탐색 정점들의 경로 길이는 양수로, 역방향 탐색 정점들의 경로 길이는 음수로 저장하도록 한다.
그리고 정점 탐색 도중 인접한 정점(이미 발견한 정점)과의 경로 길이 부호가 반대일 경우 가운데서 만났다는 것을 알 수 있다.
탐색의 방향을 경로의 길이의 부호로 판단하기 때문에, 최단 길이를 0으로 하지 않고 1과 -1로 초기화 한다.
이 때 경로의 길이가 총 2만큼 늘어났으므로,
가운데에서 만나서 최단 경로의 길이를 구할 때 2만큼 빼주고, 만난 두 정점을 이어주는 간선 하나를 추가하므로 1을 더해주도록 한다.
// 15-퍼즐을 해결하는 양방향 탐색 알고리즘
class State;
int sign(int x){
if(!x) return 0;
return x > 0? 1 : -1;
}
int inc(int x){
if(x < 0) return x - 1;
return x + 1;
}
int bidirectional(State start, State finish){
if(start == finish) return 0;
map<State, int> c; // 각 정점까지의 최단 경로 길이를 저장한다.
queue<State> q;
c[start] = 1;
c[finish] = -1;
q.push(start);
q.push(finish);
while(!q.empty()){
State here = q.front();
q.pop();
vector<State> adj = here.getAdjcent();
for(int i = 0; i < adj.size(); i++){
map<State, int>::iterator it = c.find(adj[i]); // key가 adj[i]인 element 찾기
if(it == c.end()){ // 해당 element가 존재하지 않으면 end() 포인터 반환
q.push(adj[i]);
c[adj[i]] = inc(c[here]);
}
else if(sign(it -> second) != sign(c[here])){ // 찾은 element의 값의 부호와 현재 정점의 경로 길이의 부호가 다르면
return abs(it -> second) + abs(c[here]) - 1;
}
}
}
return -1;
}
위 방법은 굉장히 유용하지만 역방향 간선을 찾아내기 어려운 문제나,
역방향 간선이 아주 많아서 역방향 탐색의 분기 수가 지나치게 큰 경우에는 사용할 수 없다.
15-퍼즐의 경우 양방향 그래프이기 때문에 양방향 탐색을 적용하기 아주 적절하다.