📍 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(a.k.a. 종만북)>으로 공부한 내용을 정리한 게시글입니다.

너비 우선 탐색(BFS, Breadth First Search)

시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘
각 정점을 방문할 때마다 모든 인접 정점을 검사하고, 처음 보는 정점을 발견하면 방문 예정이라고 기록해둔 뒤 별도의 위치에 저장. 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문 -> 큐(Queue) 사용
✔️ 예시 : 다익스트라의 최단 거리 알고리즘, 프림의 최소 스패닝 트리 알고리즘

vector<vector<int>> adj;

vector<int> bfs(int start) {
	vector<bool> discovered(adj.size(), false);	// 각 정점의 방문 여부
    queue<int> q;	// 방문할 정점의 목록을 유지하는 큐
    vector<int> order;	// 정점의 방문 순서
    discovered[start] = true;
    q.push(start);
    while(!q.empty()) {
    	int here = q.front();
        q.pop();
        order.push_back(here);
        // 모든 인접한 정점을 검사
        for(int i = 0; i < adj[here].size(); i++) {
        	int there = adj[here][i];
            if(!discovered[there]) {
            	q.push(there);
                discovered[there] = true;
            }
        }
    }
    return order;
}

BFS 스패닝 트리 : 새 정점을 발견하는 데 사용했던 간선들만을 모은 트리

최단 경로 탐색

간선 (u, v)를 통해 정점 v를 발견했을 때 시작점으로부터 v까지의 최단 거리 : distance[v] = distance[u] + 1
시작점으로부터 다른 모든 정점까지의 최단 경로는 bfs 스패닝 트리 위에서 찾을 수 있음

// start에서 각 정점까지의 최단 거리와 bfs 스패닝 트리를 계산
void bfs(int start, vector<int>& distance, vector<int>& parent) {
	distance = vector<int>(adj.size(), -1);	// start부터 i까지의 최단 거리
    parent = vector<int>(adj.size(), -1);	// bfs 스패닝 트리에서 i의 부모의 번호
    queue<int> q;	// 방문할 정점 목록을 유지하는 큐
    distance[start] = 0;
    parent[start] = start;
    q.push(start);
    while(!q.empty()) {
    	int here = q.front();
        q.pop();
        for(int i = 0; i < adj[here].size(); ++i) {
        	int there = adj[here][i];
            if(distance[there] == -1) {
            	q.push(there);
                distance[there] = distance[here] + 1;
                parent[there] = here;
            }
        }
    }
}

// v로부터 시작점까지의 최단 경로 계산
vector<int> shortestPath(int v, const vector<int>& parent) {
	vector<int> path(1, v);
    while(parent[v] != v) {
    	v = parent[v];
    	path.push_back(v);
	}
    reverse(path.begin(), path.end());
    return path;
}

양방향 탐색

• 두 정점 사이의 최단 경로를 찾을 때 사용
• 정방향 탐색과 역방향 탐색을 동시에 하며, 이 둘이 가운데서 만나면 종료
• 단순한 bfs보다 훨씬 효율적으로 최단 경로를 찾을 수 있음

양방향 탐색 가능 조건

• 양방향 탐색 가능
• 각 정점마다 가능한 역방향 간선이 많지 않아야 함

class State;
int sgn(int x) {
	if(!x) return 0;
    else return x > 0 ? 1 : -1;
}

// x의 부호 반환
int incr(int x) {
	if(x > 0) return x - 1;
    else return x + 1;
}

// x의 절대값을 1 증가
int bidirectional(State start, State Finish) {
	map<State, int> c;	// 각 정점까지의 최단 경로의 길이 저장
    queue<State> q;
    if(start == finish) return 0;
    q.push(start);
    c[start] = 1;	// 정방향 탐색인 경우 양수
    q.push(finish);
    c[finish] = -1;	// 역방향 탐색인 경우 음수
    
    while(!q.empty()) {
    	State here = q.front();
        q.pop();
        vector<State> adj = here.getAdjacent();
        for(int i = 0; i < adj.size(); ++i) {
        	map<State, int>::iterator it = c.find(adjacent[i]);
            if(it == c.end()) {
            	c[adj[i]] = incr(c[here]);
                q.push(adj[i]);
            }
            // 가운데서 만난 경우
            else if(sgn(it->second) != sgn(c[here]))
            	return abs(it->second) + abs(c[here]) - 1;
        }
    }
    return -1;
}