[BOJ - JAVA] 케빈 베이커의 6단계 법칙

# 주소

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

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

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;

public class Main {
    static int node;
    static int n, answer;
    static int arr[][];
    static boolean[] visit;
    static int[] ans;
    static int[] pp;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        node = scan.nextInt();
        n = scan.nextInt();
        arr = new int[node + 1][node + 1];
        pp = new int[node + 1];
        for (int i = 1; i <= n; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            arr[a][b] = arr[b][a] = 1;
        }
        int po = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= node; i++) {
            int sum = 0;
            for (int j = 1; j <= node; j++) {
                if (i != j) {
                    visit = new boolean[node + 1];
                    ans = new int[node + 1];
                    sum += bfs(i, j, 0);
                }
            }
            if(sum < min){
                po = i;
                min = Math.min(min, sum);
            }
        }
        System.out.println(po);
    }
    public static int bfs(int x, int y, int cnt) {
        Queue<Integer> queue =  new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();
        queue.offer(x);
        visit[x] = true;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for(int i = 1; i <= node; i++){
                if(arr[now][i] == 1 && visit[i] == false)
                    list.add(i);
            }
            Iterator<Integer> iter = list.iterator();
            while(iter.hasNext()){
                int next = iter.next();
                if(!visit[next]){
                    ans[next] = ans[now]+ 1;
                    if(next == y){
                        return ans[next];
                    }
                    visit[next] = true;
                    queue.offer(next);
                }
            }
        }
        return 0;
    }
}

클로이드 와샬 기법으로 푸는거라고 하는데 전 그냥 BFS가 나을 것 같아서 BFS로 풀었습니다.

Iterator를 처음 활용해봤는데 배열을 Iterator로 쓰려고 했다가 에러가 떠서 Iterator에 대해서 좀 공부했습니다.

기본적으로 list, set타입의 자료구조들만 반복할 수 있다는 개념의 Iterator는 기본적인 배열은 사용할 수 없습니다.

어려운 개념은 없지만 자꾸 에러가 떠서 아 뭐지 하고 있었는데 알고보니까 위에 min 값을 Integer.MIN_VALUE라고 해놨네요.

이러니 계속 정답이 0만 출력이 되지 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

한 두시간 정도 틀린게 없는데... 하면서 Iterator를 첨엔 써봤다가, queue로 해봤다가 일반 배열에도 담아 봤다가 다시 Iterator가 젤 나아서 이거 쓰는데, 그래도 에러나길래 위에 보니까 min값이 이상하더라고요. 그래서 시간이 좀 걸렸습니다.

다른거좀 풀어봐야겠어요 ㅠㅠ 내 머리도 bfs될거같아..