99클럽 코테 스터디 2일차 TIL [BFS]

- 오늘의 학습 키워드 : BFS
[문제 이름 : 케빈 베이컨의 6단계 법칙 (백준 1389, S1)]
문제 url : https://www.acmicpc.net/problem/1389

내가 작성한 코드는 아래와 같다.

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

class Main {
    static ArrayList<Integer>[] list;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        list = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list[start].add(end);
            list[end].add(start);
        }

        int minIndex = 0;
        int minValue = Integer.MAX_VALUE;
        
        // 각 사람마다 BFS 실행
        for (int i = 1; i <= n; i++) {
            int[] distances = bfs(i, n);
            int sum = 0;
            for (int j = 1; j <= n; j++) {
                sum += distances[j];
            }
            if (sum < minValue) {
                minValue = sum;
                minIndex = i;
            }
        }
        
        System.out.println(minIndex);
    }
        
    private static int[] bfs(int start, int n) {
        int[] distances = new int[n + 1];
        Arrays.fill(distances, -1); // 초기값 -1로 설정
        Queue<Integer> queue = new LinkedList<>();
        
        queue.offer(start);
        distances[start] = 0;
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int neighbor : list[current]) {
                if (distances[neighbor] == -1) { // 아직 방문하지 않은 노드인 경우
                    distances[neighbor] = distances[current] + 1;
                    queue.offer(neighbor);
                }
            }
        }
        
        return distances;
    }    
}

[풀이 과정] - (풀이 시간: 30분)
각 사람마다 모두 bfs를 돌려가며, 최단 거리를 계산한다.
계속 합을 비교해가며, 최소 인덱스를 찾아주면 된다.


내일은 필기 시험을 대비한 전공 필기를 공부할 예정이다.