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

 

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

#include <stdio.h>

const int MAX_F = 100;

int N, M;
int map[MAX_F + 10][MAX_F + 10];
int result[MAX_F + 10][MAX_F + 10];
int queue[MAX_F + 10][2];
int s, e;

void init() {
  scanf("%d %d", &N, &M);

  int s, e;

  for (int m = 0; m < M; ++m) {
    scanf("%d %d", &s, &e);
    map[s][e] = 1;
    map[e][s] = 1;
  }
}

void bfs(int n) {
  s = 0; e = 0;

  queue[e][0] = n;
  queue[e++][1] = 0;

  while (s <= e) {
    int node = queue[s][0];
    int cnt = queue[s++][1];

    for (int i = 1; i <= N; ++i) {
      if (n == i) { continue; }
      if (map[node][i] && result[n][i] == 0) {
        result[n][i] = cnt + 1;
        queue[e][0]= i;
        queue[e++][1] = cnt + 1;
      }
    }
  } 
}

void print() {
  int min = MAX_F * MAX_F;
  int R = 0;

  for (int i = 1; i <= N; ++i) {
    int sum = 0;

    for (int j = 1; j <= N; ++j) {
      sum += result[i][j];
    }

    if (min > sum) {
      min = sum;
      R = i;
    }
  }

  printf("%d", R);
}

int main(void) {
  //freopen("1389.txt", "r", stdin);

  init();


  for (int n = 1; n <= N; ++n) {
    bfs(n);
  }

  print();

  return 0;
}

 

오랜만에 푸니까 BFS 왤케 어렵냐