[백준 1389] 케빈 베이컨의 6단계 법칙

1. BFS+vector+pair

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
vector<int> v[102];
vector<pair<int,int>> ans;
queue<int> q;
int visited[102];
int n,m,a,b,temp;
 
bool cmp(const pair<int,int> &a, const pair<int,int>&b){
    return a.second<b.second;
}
void bfs(){
    while(!q.empty()){
        int node=q.front(); q.pop();
        temp+=visited[node];
        
        for(int i=0; i<v[node].size(); i++){
            int next=v[node][i];
            
            if(visited[next]==-1){
                visited[next]=visited[node]+1;
                q.push({next});
            }
        }
    }
}
 
int main(void){
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++){
        scanf("%d %d", &a, &b);
        
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    for(int i=1; i<=n; i++){
        memset(visited,-1,sizeof(visited));
        visited[i]=0; temp=0;
        q.push({i});
        bfs();
        ans.push_back(make_pair(i,temp));
    }
    
    sort(ans.begin(), ans.end(),cmp);
    
    printf("%d", ans[0].first);
    return 0;
}

 

코드가 더럽지만 할 수 있지만 vector랑 pair에 좀 익숙해지고 싶었다.

 

 

2. DFS

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> v[102];
int visited[102];
int ans[102];
int n,m,a,b,temp,minTot;
void dfs(int node){
    for(int i=0; i<v[node].size(); i++){
        int next=v[node][i];
 
        if(visited[next]==-1 || visited[next]>visited[node]+1){
            visited[next]=visited[node]+1;
            dfs(next);
        }
    }
}
int main(void){
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++){
        scanf("%d %d", &a, &b);
        
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    for(int i=1; i<=n; i++){
        memset(visited,-1,sizeof(visited));
        visited[i]=0; temp=0;
 
        dfs(i);
        
        for(int i=1; i<=n; i++)
            temp+=visited[i];
        
        ans[i]=temp;
    }
    
    temp=ans[1];
    minTot=1;
    
    for(int i=2; i<=n; i++){
        if(ans[i]<temp){
            temp=ans[i];
            minTot=i;
        }
    }
    
    printf("%d",minTot);
 
    return 0;
}

 

DFS는 41번째 줄 안 넣어줬다가 틀렸습니다 떠서 처음에 멘붕ㅋㅋㅋㅋㅠㅠ

초기화를 잘하자..

 

 

3. 플로이드 와샬 알고리즘

#include<cstdio>
using namespace std;
int arr[102][102];
int a,b,n,m,result,temp,minTot=99999999;
int main(void){
    scanf("%d %d", &n, &m);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i!=j)
                arr[i][j]=99999999;
        }
    }
    for(int i=0; i<m; i++){
        scanf("%d %d", &a, &b);
        
        arr[a][b]=1;
        arr[b][a]=1;
    }
    
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=0; j<=n; j++){
                if(arr[i][j]>arr[i][k]+arr[k][j])
                    arr[i][j]=arr[i][k]+arr[k][j];
            }
        }
    }
    
    for(int i=1; i<=n; i++){
        temp=0;
        for(int j=1; j<=n; j++)
            temp+=arr[i][j];
        
        if(minTot>temp){
            minTot=temp;
            result=i;
        }
        
    }
    
    printf("%d\n", result);
    return 0;
}

 

사실 난 BFS, DFS(최소거리니까 DFS보다는 BFS로 푸는게 더 나을수도 있음)로 풀고 끝~ 이랬는데 알고보니 플로이드 와샬 알고리즘을 쓰면 쉽다고 한다.

나처럼 몰랐던 사람들은 마이구이님 블로그 가서 기본을 다지자

 

 

4. 자바 - 플로이드 와샬 알고리즘

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main{
    static int maxNum = 1000000000;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        // 입력받기
        StringTokenizer st;
        st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] dist = new int[n+1][n+1];
 
        // 초기화
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++)
                dist[i][j] = maxNum;
        }
 
        // 친구관계 입력받기
        int a=0, b=0;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
 
            dist[a][b] = 1;
            dist[b][a] = 1;
        }
 
        // 플로이드 와샬 알고리즘
       for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                        dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
 
        // 케빈 베이컨 수 구하기
        int sum=987654321, ans=0;
        for(int i=1; i<=n; i++){
            int temp=0;
            for(int j=1; j<=n; j++){
                if(i!=j) 
                    temp += dist[i][j];
            } 
            
            // i의 케빈 베이컨 수가 가장 작다면 sum과 ans 
            if(sum>temp){
                sum = temp;
                ans = i;
            }
        }
 
        System.out.println(ans);
    }
}