BOJ::1389 케빈 베이컨의 6단계 법칙

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


알고리즘 분류에 dfs,bfs,플로이드 와샬 알고리즘 이라고 적혀있긴 한데

dfs로는 어떻게 푸는지 모르겠다.


쉽게 푸는건 플로이드 와샬 알고리즘 이고 이문제에서 속도 차이는 나지 않았다.


위가 플로이드 와샬, 아래가 bfs



<bfs를 이용 한 풀이>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Main{
    static int n,m;
    static int map[][]=new int[101][101];
    static boolean check[];
    static int res[]=new int[101];
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        
        for(int i = 0 ; i < m ; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y]=1; map[y][x]=1;
        }
        
        for(int i =1 ; i<= n ;i++){
            check = new boolean[n+1];
            bfs(i);
        }
        
        int min = Integer.MAX_VALUE;
        for(int i=1;i<=n;i++){
            if(res[i]<min){
                min = res[i];
            }
        }
        for(int i = 1 ; i<= n ; i++){
            if(res[i]==min){
                System.out.println(i);
                break;
            }    
        }
    }
    //떨어진 거리를 체크하기 위해 Node 클래스를 만들었다
    //dist = 떨어진 거리
    //그래서 res 배열에 dist 만큼씩 더해주도록 만들어 보았다.
    public static void bfs(int v){
        Queue<Node> q = new LinkedList();
        check[v]=true;
        q.add(new Node(v,0));
        
        while(!q.isEmpty()){
            int x = q.peek().x;
            int dist = q.poll().dist;
            for(int i = 1 ; i<= n;  i++){
                if(map[x][i] ==1 && !check[i]){
                    q.add(new Node(i,dist+1));
                    check[i]=true;
                    res[i]+=dist+1;
                }
            }
        }
    }
}
class Node{
    int x;
    int dist;
    Node(int _x, int d){
        x=_x;
        dist=d;
    }
}
cs



<플로이드 와샬 알고리즘을 이용한 풀이>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
    static int n,m;
    static int map[][]=new int[101][101];
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++){
                map[i][j]=(i==j)?0:9999999;
            }
        }
        
        for(int i = 0 ; i < m ; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y]=1; map[y][x]=1;
        }
        
        //각각 경로에 대해 최단경로를 만들어준다.
        //ex)1행 -> 1-1의 최단경로 1-2의 최단경로 1-3의 최단경로 1-4의 최단경로 .....
        for(int k = 1 ; k<= n ; k++){
            for(int i = 1 ; i <= n ; i++){
                for(int j = 1 ; j <= n ; j++){
                    if(map[i][j]> map[i][k]+map[k][j]){
                        map[i][j]=map[i][k]+map[k][j];
                    }
                }
            }
        }
        
        int res[] = new int[n+1];
        int min = Integer.MAX_VALUE;
        
        for(int i = 1 ; i<= n ; i++){
            int sum=0;
            for(int j = 1 ; j<= n ; j++){
                sum+=map[i][j];
            }
            res[i]=sum;
            if(sum<min){
                min = sum;
            }
        }
        
        for(int i = 1 ; i<= n ; i++){
            if(res[i]==min){
                System.out.println(i);
                break;
            }
        }
    }
}
 
cs


저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

1475 방 번호  (0) 2017.12.31
1463 1로만들기  (0) 2017.12.31
1325 효율적인 해킹  (0) 2017.12.31
1309 동물원  (0) 2017.12.31
1302 베스트 셀러  (0) 2017.12.31

+ Recent posts

티스토리툴바