Baekjoon 1389번 케빈 베이컨의 6단계 법칙

문제

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

걸린 시간

01 : 20 : 15

풀이

C++

#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 101
using namespace std;

int bfs(int adj_mat[][MAX], int i, int j){
    queue<pair<int, int>> q;
    q.push(make_pair(i, 0));    
    pair<int, int> tmp;
    int v, l;
    int visited[MAX] = {0};
    visited[i] = 1;

    while(!q.empty()){
        tmp = q.front();
        v = tmp.first; // value
        l = tmp.second; // length
        q.pop();

        l += 1;

        if(v == j)
            break;

        for(int w = 0; w < MAX; w++){
            if(!visited[w] && adj_mat[v][w]){
                q.push(make_pair(w, l));
            }
        }
    }

    return l-1;
}

int main(){
    int N, M;
    scanf("%d %d", &N, &M);

    int adj_mat[MAX][MAX] = {0};
    int A, B;
    while(M--){
        scanf("%d %d", &A, &B);
        adj_mat[A][B] = 1;
        adj_mat[B][A] = 1;
    }

    map<int, vector<int>> m;
    vector<int> tmp;
    int acc;
    for(int i = 1; i < N+1; i++){ // 비교할 정점
        acc = 0;
        for(int j = 1; j < N+1; j++){ // 나머지 정점
            acc += bfs(adj_mat, i, j);
        }

        if(m.find(acc) == m.end()){
            tmp = {};
            tmp.push_back(i);
            m.insert(make_pair(acc, tmp));
        }
        else{
            m[acc].push_back(i);
        }
    }

    printf("%d\n", m.begin()->second[0]);

    return 0;
}

기본적인 그래프 탐색 문제로 인접행렬과 bfs 를 사용해 풀이했다.

문제 중간에 디버깅을 위한 printf 문 한줄 때문에 맞는 정답임에도 틀렸습니다가 출력되어 한참을 다시 검토했다...

다른 풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n, m;
int adj[101][101];
vector<pair<int, int>> result;

void floyd(){
    for(int i = 1; i <= n; i++)
        adj[i][i] = 0;
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            adj[i][j] = INF;
    int a, b;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        adj[a][b] = 1;
        adj[b][a] = 1;
    }
    floyd();
    for(int i = 1; i <= n; i++){
        int val = 0;
        for(int j = 1; j <= n; j++)
            val += adj[i][j];
        result.push_back(make_pair(val, i));
    }
    sort(result.begin(), result.end());
    cout << result[0].second;
    return 0;
}

모든 정점 쌍의 최단거리를 간단히 구할 수 있는 플로이드 와샬(Floyd Warshall) 알고리즘을 이용한 풀이이다.