[백준 18243] Small World Network [Java]

문제

http://boj.ma/18243

18243번: Small World Network

 

---

풀이

문제 요약

N명의 관계에 대해 누구든 6단계를 넘어 연결된 네트워크인지 확인하자.

아이디어

K개의 관계로 이루어진 양방향 그래프에 대해 임의의 번호에서 어떤 번호로든 6단계를 초과하는지 확인해야 한다.

임의의 모든 위치에서 bfs를 수행하거나, floyd warshal로 최단 거리를 구해서 해결할 수 있다.

    private static int floydWarshall(int[][] graph, int N) {
        for (int k = 1; k <= N; ++k) {
            for (int i = 1; i <= N; ++i) {
                for (int j = 1; j <= N; ++j) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }

        int res = 0;
        for (int i = 1; i <= N; ++i) {
            for (int j = i; j <= N; ++j) {
                res = Math.max(res, graph[i][j]);
            }
        }
        return res;
    }

풀이 시간

10분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/18243.java

problem-solving/baekjoon-online-judge/easy/18243.java at main · rogi-rogi/problem-solving