[Java] 플로이드–워셜 | 백준 2660 회장뽑기

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

 

접근 방식 :

"다른 회원들과 가까우 정도", "친구의 친구" 등의 부분을 읽었을 때, 스터디 1, 2일차에 학습했던 플로이드워셜 알고리즘을 적용해야 된다는 것이 바로 느껴졌다.

 

어느 회원의 점수가 n점이면 다른모든 회원이 친구이거나, ... , [친구의]*(n-1) 친구임을 말한다고 이해했고, 즉 n점이면 최적의 관계를 구했을 때 해당 회원으로 부터 가장 멀리 떨어져 있는 회원은 n-1개의 다른 친구(노드들)을 거쳐서 연결된다는 의미로 해석했다.

 

각 노드에서 다른 노드들로의 최적의 경로를 구한뒤,

각 노드에서 가장 멀리 떨어져있는 노드와의 간선 수가 그 노드의 점수가 된다.

 

이렇게 문제를 해석하니 백준 1389 케빈 베이컨의 6단계 법칙과 각 노드에서 다른 노드들로의 최적의 경로를 구하는 과정까지 완전히 동일한 문제가 됐다.

 

다른 점은 백준 1389 케빈 베이컨의 6단계 법칙에서는 해당 노드와 다른 노드들과의 총 거리를 합했다면, 이번엔 거리들중 최대값을 그 노드의 점수로 정하고, 점수가 가장 낮은 노드들을 구한다는 것 밖에 없다.

 

 

우선 friend 배열을 선언하고 최악을 경우로 배열 값을 초기화 시켰다. 문제에서 회원의 수가 50명이 최대라고 하였으므로 최대 49개의 간선을 거칠 수 있어 49로 모든 값을 초기화시켰다. 여기서 처음 제출할때 실패 원인이 되는 부분이 발생했는데, friend[i][i], 즉 자기 자신과의 거리를 0으로 두지 않아 이후 플로이드워셜을 적용할 때 올바르게 동작하지 않았다.

friend = new int[N + 1][N + 1];

for(int i=1; i<=N; i++){
    Arrays.fill(friend[i], 49);
    friend[i][i] = 0;
}

 

직접 연결된 관계들 1로 업데이트

while (true) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int u1 = Integer.parseInt(st.nextToken());
    int u2 = Integer.parseInt(st.nextToken());

    if (u1 == -1 && u2 == -1) break;

    friend[u1][u2] = friend[u2][u1] = 1;
}

 

플로이드워셜 알고리즘 적용

for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (friend[i][j] > friend[i][k] + friend[k][j] ) {
                friend[i][j] = friend[i][k] + friend[k][j];
            }
        }
    }
}

 

이부분까지 왔을 때 배열 friend의 1행부터 n행에는 각각 회원번호 1과 다른 회원들 사이의 거리들 ~ 회원번호 n과 다른 회원들 사이의 거리들의 최적의 결과가 들어있을 것이다.

 

이제 각 회원 번호의 점수를 정해주기 위해 각 행에서 가장 큰(거리가 먼) 점수를 찾아 그것의 그 회원 번호의 점수로 지정했다.

int[] userScore = new int[N + 1];

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        userScore[i] = Math.max(friend[i][j], userScore[i]);
    }
}

그렇게 구한 회원 번호의 점수들 중 가장 낮은 점수들 중 가장 작은 점수를 구하였다. 지금 생각해보니 이 부분은 회원 번호의 점수를 정하는 과정과 합치면 더 간단해질 수 있겠다. (min = Math.min(userScore[i],min)) 이 부분을 회원 번호 i의 for(int j =1; j<=N; j++) 루프가 끝날때 마다 다음 회원번호로 넘어가기전 최소 점수를 업데이트하면 되겠다.)

int min = 49;
for (int i = 1; i <= N; i++) {
    min = Math.min(userScore[i], min);
}

System.out.print(min + " ");

그다음 최소 점수를 가진 회원 수를 구하였고

int cnt = 0;
for (int i = 1; i <= N; i++) {
    if (userScore[i] == min) cnt++;
}
System.out.println(cnt);

그 최소 점수에 해당 되는 회원번호를 출력해 주었다.

for (int i = 1; i <= N; i++) {
    if (min == userScore[i]) System.out.print(i + " ");
}

 

 

느낀점 : 

같은 유형인 플로이드워셜 알고리즘 문제를 3일째 푸니 처음 플로이드워셜 문제를 풀었을 때보다 더 익숙해진 느낌이여서 좋았고, 앞으론 더 최적화된 코드를 작성하기 위한 고민을 해보아야겠다.