99클럽 코테 스터디 2일차 - 백준, 케빈 베이컨의 6단계 법칙

 

문제

=

풀이

문제 해석

1. 케빈 베이컨의 6단계 법칙은 "지구에 있는 모든 사람들은 6단계 이내에서 서로 아는 사람으로 연결될 수 있다."라는 법칙이다.

2. 케빈 베이컨 게임은 임의의 두사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

3. 사람의 번호는 1부터 N까지이고, 승리자는 가장 작은 단계의 합을 가지고 있는 사람이다.

4. 첫째 줄에 게임유저의 수 N, 관계의 수 M 이 주어진다.

5. 둘째 줄 부터 관계 M개가 주어진다.

6. 게임의 승리자를 찾아라, 같은 사람이 여려 명일 경우 숫자가 작은 사람이 이긴다. 

문제 풀이

1. 유저의 수가 100이하이고 모든 유저와의 관계를 나타내야 하므로 플로이드-워셜 알고리즘을 사용

2. 플로이드-워셜의 알고리즘의 내부 조건으로는 x(출발),y(중간다리),z(도착) 가 있을 때 

  - x와 y의 관계 있음 y와 z관계있음

    - x와 z 관계있음

      - 현재 관계와 x와 y, y와 z의 관계의  값 중 작은 값을 넣어줌 

    - x와 z 관계없음

      - x와 y, y와 z의 관계의 수를 더해서 넣어줌

소스코드

package online.judge.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 케빈 베이컨의 6단계 법칙
 *
 * 문제 해석
 * 1. 6 관계만 거치면 모든 사람과 연결된다는 6단계 법칙을 문제로 만든 것이다.
 * 2. 케빈베이컨 게임은 모인사람들과의 단계의 합이 가장 적은 사람이 이기는 게임이다.
 * 3. 가장 작은 단계의 합을 가진 사람을 구하라
 *
 * 문제 풀이
 * 1. N이 100이하이므로 플로이드-워셜 사용
 * 2. 거치는 관계가 있을 때 조건문 추가
 *  - 닿아있지 않다면 거치는 관계를 넣어줌
 *  - 닿아있다면 원래 값과 거치는 값 중 작은 값을 넣어줌
 */
public class No1389 {
    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());

        int[][] graph = new int[n][n];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        //플로이드-워셜
        for (int i = 0; i < n; i++) {// 거쳐가기
            for (int j = 0; j < n; j++) {// 출발
                for (int k = 0; k < n; k++) {// 도착
                    if(graph[j][i]!=0 && graph[i][k] !=0){
                        if(graph[j][k] == 0){
                            graph[j][k] = graph[j][i] + graph[i][k];
                        }else{
                            graph[j][k] = Math.min(graph[j][k],
                                    graph[j][i] + graph[i][k]);
                        }
                    }
                }
            }
        }

        int minValue = Integer.MAX_VALUE;
        int answer = -1;
        for (int i = 0; i < n; i++) {
            int sum =0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                sum += graph[i][j];
            }
            if(sum < minValue){
                answer = i+1;
                minValue = sum;
            }
        }

        System.out.println(answer);
    }
}

TIL

• 플로이드-워셜을 사용해야 하는 문제를 명확히 파악할 수 있게 되었음
• 문제를 코드로 치환할 때 조건을 항상 빠지지 않는지 오류는 없는지 체크를 해야 함