BFS와 그를 응용한 다익스트라를 정리한다.

BFS

https://programmers.co.kr/learn/courses/30/lessons/43162

네트워크간에 걸리는 시간, 경로는 상관없이 탐색을 하기만 하면 되므로 BFS를 이용하여 풀 수 있다.
DFS는 map을 주어줄 경우, BFS는 노드 간의 연결을 줄 때 많이 사용하는 것 같다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    int visited[210] = {0};
    queue<int> q;
    
    //1. 큐에 노드를 넣는다.
    for(int i=0;i<n;i++){
        if(!visited[i]) {
            answer++;
            visited[i] = 1;
            q.push(i);
        } 
        
        //bfs
        while(!q.empty()){
        	// 2. 가장 앞의 노드를 가져온다.
            int now = q.front();
            q.pop();
            
            for(int j=0;j<n;j++){
            	// 3. 방문하지 않은 연결된 모든 노드를 찾는다.
				if(now!=j && computers[now][j] == 1 && visited[j]==0){
                	//4. 방문했다고 체크하고 큐에 집어넣는다.
                    q.push(j);
                    visited[j] = 1;
                }
            }
        }
    }
    
    return answer;
}

bfs는 이런 식으로 되어 있다.
1. 맨 처음에 큐에 노드를 넣는다.

• 이 문제는 저번 dfs 단지 문제처럼 노드간 연결이 분리되어있고, 그걸 다 순회해야하기 때문에 for문을 돌리면서 방문하지 않았던 것들만 큐에 넣는다.

2. 가장 앞의 노드를 가져온다.
3. 방문하지 않은 연결된 모든 노드를 찾는다.

• 인접행렬을 for문으로 순회한다.

4. 방문했다고 체크하고 큐에 집어넣는다.

반드시 필요한 경우

가장 짧은, 최솟값의 경우에 BFS가 필수적이다.
말이 되고픈 원숭이
위의 문제를 DFS로 풀면 시간초과가 발생한다. 한 노드에서 경로를 끝까지 진행해보고 실패할 경우에 리턴하기 때문이다. 따라서 16이 최악의 상황이라면 BFS에서는 거리를 1씩 늘려가면서 방문하므로 결과적으로 방문하지 않지만, DFS에서는 맨 처음에 방문하게 될 수도 있다.
따라서 이런 상황에서는 BFS를 사용하여야 한다.

다익스트라

https://www.acmicpc.net/problem/1753

#include <stdio.h>
#include <queue>
#include <functional>
#include <vector>
using namespace std;
priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int>>> h;
vector<pair<int, int>> G[20001];
int dist[20001];
int check[20001];

int main() {
	//입력
	int V,E;
	int s;
	scanf("%d %d", &V, &E);
	scanf("%d", &s);
    //1. 큐에 노드를 넣는다.
	h.push({ 0,s });
	for (int i = 0; i < E; i++) {
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		G[u].push_back({ v,c });
	}
	for (int i = 1; i <= V; i++) {
		dist[i] = 123456789;
	}
	dist[s] = 0;

	//bfs
	while (!h.empty()) {
    	//2. 가장 앞의 노드를 가져오고, 방문했다고 표시한다.
		int here = h.top().second;
		int cost = h.top().first;
		h.pop();
		check[here] = 1;

		// 3. 방문하지 않은 연결된 모든 노드를 찾는다.
		for (int i = 0; i < G[here].size(); i++) {
			int next = G[here][i].first;
			int next_cost = G[here][i].second + cost;
			if (check[next] == 1)continue;
			
            //4. 큐에 집어넣는다.
            if (next_cost < dist[next]) {
				dist[next] = next_cost;
				h.push({ next_cost,next });
			}
		}
	}

	for (int i = 1; i <= V; i++) {
		if (dist[i] == 123456789)
			printf("INF\n");
		else
			printf("%d\n", dist[i]);
	}
	return 0;
	
}

구현 방법

C++에서는 priority_queue를 이용해 min heap을 만들어서 이용했다. 가장 cost가 낮은 것들이 힙의 맨 앞에 와야 했기 때문이다.

위의 BFS 문제와의 차이

위의 BFS에서는 인접 행렬을 이용해 진행했지만, 여기서는 노드와의 연결을 입력으로 받아 인접 리스트를 만들어서 진행하였다. 물론 이건 문제 by 문제

구현

include

#include <queue>
#include <functional> // greater으로 내림차순 정렬을 해야 하므로
#include <utility> // pair

min_heap 선언

priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int>>> h;

고민했던 부분

이 코드에서 가장 궁금했던 부분은 여기서는 왜 방문했다는 표시를 큐에 넣을 때 하면 안되냐는 것이었다.
결과적으로 아까 bfs의 경우에는 표시를 반드시 큐에 넣을때도 진행해야 했다. 왜냐하면 거기서의 포문은 이 노드가 네트워크에 연결되어 있는지 확인하는 포문이어서 방문하면 안된다는 표시를 남겨야 했기 때문이다.
하지만 다익스트라의 경우에는 방문해서 3번을 진행해야 했다. 따라서 거기서 표시를 남기면 안 됐다.