[Java] 플로이드–워셜 | 백준 1389 케빈 베이컨의 6단계 법칙

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

 

첫 접근 방식(실패)

플로이드 워셜 알고리즘을 적용할 수 있을 것 같은 느낌이 들었지만 이를 구현하기 막막해 브루트포스 방식으로 풀어보았고 결과는 역시 실패였다. 

대략 아래와 같은 방식으로 접근했었다. 

1. 모든 가능한 노드 쌍 (i, j)에 대해 반복하며 연결 찾기
2. searchMin 함수를 통한 탐색
3. 각 연결되지 않은 노드 쌍에 대해 searchMin 함수를 호출하여 중간 노드 찾기
4. 모든 가능한 경로를 탐색하고 최소값을 갱신

 

예제 입력과 출력은 올바르게 나올 수 있었지만 시간 초과 등의 문제로 실패하였다.

 

 

다시 플로이드 워셜 학습하고 풀이한 내용을 정리해 본다.

내가 브루트포스 방식으로 접근했을때도 결국 연결되지 않은 유저 쌍을 이을 수 있는 중간 유저를 구하는 것이 목적이였다.

=> 플로이드 워셜 방식을 어떻게 적용해야될지 정확히 몰라 어려웠던것 같다.

 

우선 유저 최적 관계를 저장할 수 있는 2차월 배열을 생성한다. 모든 값을 최대 관계수인 5000으로 채우고, i행 i열 자기 자신과의 관계는 0으로 설정한다.

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

 

다음 단계로 M개의 친구 관계를 바로 연결되어 있는 관계이므로 1로 업데이트한다.

관계가 u1 u2 일 경우 => u1 행 u2열, u2행 u1열을 1로 업데이트

for(int i=0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int u1 = Integer.parseInt(st.nextToken());
    int u2 = Integer.parseInt(st.nextToken());
    bacon[u1][u2] = bacon[u2][u1] = 1;
}

 

이제 플로이드 워셜 알고리즘을 적용할 단계다.

거처갈 유저를 k로 하고, i 와 j 사이의 관계가 i 와 k 사이의 관계 + k 와 사이의 관계보다 크다면 k를 통한 관계가 더 작은 단계를 거치므로 이로 없데이트 한다. (i == j 인 경우는 0으로 저장해 놓았기 때문에 어떤 경우에도 양수로 업데이트 될 수 없다)

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

 

마지막으로 각 행의 합 중 최소 값을 가지는 user를 출력해주면 정답을 출력할 수 있다. 합의 최소값이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다 했으므로,

유저 1부터 순회하여 min > sum 일 경우에만 유저 번호를 업데이트하여 합의 최소값이 동일한 유저도 번호가 큰 유저이므로 무시하면 된다.

int min = Integer.MAX_VALUE;
int user = 0;
for(int i = 1; i <= N; i++){
    int sum = 0;
    for(int j = 1; j <= N; j++){
        sum += bacon[i][j];
    }
    if(min > sum) {
        min = sum;
        user = i;
    }
}

System.out.println(user);

 

 

배운점 :

플로이드 워셜 알고리즘을 아직 완벽하게 이해하지 못했다는 것을 알았다. 알고리즘을 대충 이해서는 같은 알고리즘 유형의 문제라도 계속 틀릴 수 있기 때문에 정확하게 문제와 해당 알고리즘의 핵심을 짚는 노력을 해야겠다.

i 와 j 사이의 단계와 (i 와 k 사이의 단계 + k 와 j사이의 단계), 어제 풀어보았던 정점 i에서 j로 가는 길이가 양수인 경로 두 문제는 공통적으로 결국 모든 노드와 노드간의 최단 경로를 찾는 것을 목표로 한다. 관련 문제를 더 풀어보며 플로이드 워셜 알고리즘을 더 확실하게 이해해보아야겠다.