케빈 베이컨의 6단계 법칙 (BJ_1389)

1. 문제 링크

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

 

---

 

2. 나의 코드

메모리: 14868 kb
시간: 116 ms
코드 길이: 1990 B
시간 복잡도 : O(N + M)
설명
- BFS 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_1389 {

    static int N, M;
    static ArrayList<ArrayList<Integer>> relationshipList;
    static boolean[] visited;
    static int result, minBaconCnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        relationshipList = new ArrayList<>();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        minBaconCnt = Integer.MAX_VALUE;

        for (int i = 0; i <= N; i++) {
            relationshipList.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            relationshipList.get(a).add(b);
            relationshipList.get(b).add(a);
        }

        for (int i = 1; i <= N; i++) {
            int baconCnt = bfs(i);
            if (baconCnt < minBaconCnt) {
                minBaconCnt = baconCnt;
                result = i;
            }
        }
        System.out.println(result);
    }

    private static int bfs(int i) {
        Queue<int[]> q = new LinkedList<>();
        visited = new boolean[N + 1];
        q.offer(new int[]{i, 0});
        visited[i] = true;
        int baconCnt = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            baconCnt += now[1];

            for (int people : relationshipList.get(now[0])) {
                if (visited[people]) continue;
                q.offer(new int[] {people, now[1] + 1});
                visited[people] = true;
            }
        }

        return baconCnt;
    }
}

 

---

 

3. 정답 코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N, M;
	static int[][] rel;
	static final int INF = 999999999;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		rel = new int[N+1][N+1]; //1~N번이라 +1
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				rel[i][j] = INF;
				if(i == j) rel[i][j] = 0;
			}
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			rel[a][b] = 1; //양방향
			rel[b][a] = 1;
		}
		
		for(int k=1;k<=N;k++) { //중간지점
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {
					rel[i][j] = Math.min(rel[i][j], rel[i][k]+rel[k][j]);
				}
			}
		}
		int temp = INF;
		int result = 0;
		for(int i=1;i<=N;i++) {
			int total = 0;
			for(int j=1;j<=N;j++) {
				total += rel[i][j];
			}
			
			if(temp > total) { //커야하니까 작은 index 처리도 가능
				temp = total;
				result = i;
			}	
		}
		
		bw.write(result+"");
		bw.flush();
		bw.close();
	}

}

 

---

 

4. 배운 점

- 인접 리스트 BFS, DFS의 시간복잡도는 O(V  + E)

- 인접 행렬의 BFS, DFS의 시간복잡도는 O(V^2)

- BFS는 큐, DFS는 재