백준온라인저지(BOJ)/#2644/촌수계산/BFS

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

2644번: 촌수계산

간선으로 이어진 노드간 거리를 측정하기 위해선 BFS가 효과적이다. 

측정하고자 하는 시작 노드(Start)와 도착지점 노드(Target)을 인자로 받아 두 노드간 거리를 리턴해주는 BFS Function을 설계하였다. 

핵심은 Dist[] 이고, dist[i]는 i번째 노드와 기준 start 노드간의 거리를 나타낸다.

 

[구현코드1_Adjacency Matrix]

---

#include <vector>
#include <queue>
#include <iostream>

using namespace std;
int N, start, target, E;
vector<vector<int>> adj; // Set Adjacency Matrix
vector<int> dist; // Distance list Based on Starting Point

int bfs(int start, int target){
    queue<int> q;
    dist = vector<int>(N+1,-1);
    dist[start] = 0;
    q.push(start);
    
    while(!q.empty()){
        int here = q.front();
        q.pop();
        
        for(int i = 0; i < adj[here].size(); i++){
            if(adj[here][i] == 1 && dist[i] == -1){
                q.push(i);
                dist[i] = dist[here]+1;
            }
        }
    }
    return dist[target];
}

int main(){
    cin>>N;
    adj.resize(N+1,vector<int>(N+1,0));
    cin>>start>>target;
    cin>>E;
    for(int i = 0; i < E; i++){
        int a, b;
        cin>>a>>b;
        adj[a][b] = 1;
        adj[b][a] = 1;
    }
    cout<<bfs(start, target);
    return 0;
}

 

[구현코드2_Adjacency List]

#include <vector>
#include <queue>
#include <iostream>

using namespace std;
int N, start, target, E;
vector<vector<int>> adj; // Set Adjacency List
vector<int> dist; // Distance list Based on Starting Point

int bfs(int start, int target){
    queue<int> q;
    dist = vector<int>(N+1,-1);
    dist[start] = 0;
    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(dist[there] == -1){
                q.push(there);
                dist[there] = dist[here]+1;
            }
        }
    }
    return dist[target];
}

int main(){
    cin>>N;
    adj.resize(N+1);
    cin>>start>>target;
    cin>>E;
    for(int i = 0; i < E; i++){
        int a, b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cout<<bfs(start, target);
    return 0;
}

 

Adjacency List가 공간복잡도가 더 적다. 인접한 노드 리스트만 추가하면 되므로 (간선의 개수)*2 만큼의 공간 복잡도를 갖는다. 

이에 반해, Adjacency Matrix는 공간복잡도가 (Node의 수) * (Node의 수) 만큼, 즉 Vertex, Edge로 본다면 V*V이다.

실제 제출해도 메모리 차이가 남을 볼 수 있다. (아래 캡쳐 참조/ 메모리가 적은 쪽이 Adjacency List 그래프로 구현한 코드)