[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++)

BFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int people;
int relation;
int s, e;
int ans;
 
queue<int> q;
int visited[110];
 
void BFS()
{
    visited[s] = 1;
    q.push(s);
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        
        if(now == e)
        {
            return;
        }
        
        for(int i = 1; i <= people; i++)
        {
            if(map[now][i] == 1 && visited[i] == 0)
            {
                visited[i] = visited[now] + 1;
                q.push(i);
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2644_input.txt", "r", stdin);
 
    cin >> people;
    cin >> s >> e;
    cin >> relation;
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        cin >> a >> b;
        
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    BFS();
    
    if(visited[e] == 0)
    {
        cout << -1;
    }
    else
    {
        cout << visited[e]-1;    
    }
 
    return 0;
}

 

Floyd-Warshall

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int visited[110][110];
int people;
int relation;
int s, e;
int ans;
 
void floyd()
{
    for(int k = 1; k <= people; k++)
    {
        for(int i = 1; i <= people; i++)
        {
            for(int j = 1; j <= people; j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                if(map[i][k] != 0 && map[k][j] != 0 && visited[i][j] == 0)
                {
                    visited[i][j] = 1;
                    visited[j][i] = 1;
                    
                    map[i][j] = map[i][k] + map[k][j];
                    map[j][i] = map[i][k] + map[k][j];
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2644_input.txt", "r", stdin);
 
    cin >> people;
    cin >> s >> e;
    cin >> relation;
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        cin >> a >> b;
        
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    floyd();
    
    if(map[s][e] == 0)
    {
        cout << -1;
    }
    else
    {
        cout << map[s][e];    
    }
 
    return 0;
}