[C] 1389: 케빈 베이컨의 6단계 법칙

일단 인접행렬로 그래프를 저장한다음에 for문을 이용하여 언제가 베이컨 수가 가장 작은지를 확인해봤다.

 

나아진 점1: 처음에 bfs를 돌릴때 queue에다가 먼저 놓고 bfs함수를 호출함으로써 dfs와 bfs를 섞어쓰던 실수를 없앴다!

나아진 점2: bfs함수에서 beacon_number을 구할때 따로 배열을 만들어 몇번째에 beacon_number에 넣었는지 저장해두었는데 이번에는 beacon_number[i]=beacon_number[tmp]+1; 를 사용하여 배열 2개로 저장하던걸 1개로 저장하여 효율성을 높였다.

나아진점 3: bfs 만드는 속도가 빨라졌고 continue의 사용을 적절히 했다!

 

그리고 그래프에서의 최단거리를 구할 때는 항상 BFS를 쓴다는 것을 잊어버리면 안된다!!

 

#include <stdio.h>
#include <string.h>

int arr[101][101];
int queue[10000000];
 int beacon_number[101];

void clear()
{
  for(int i=0;i<=100;i++)
    beacon_number[i]=0;
  for(int i=0;i<10000000;i++)
    queue[i]=0;
}

void bfs(int front,int rear,int cnt,int n)
{
  while(front<rear)
  {
    int tmp=queue[front];
    for(int i=1;i<=n;i++)
      {
        if(arr[tmp][i]==1 && beacon_number[i]==0)  //아직 한번도 안간 애!
        {
          queue[rear++]=i;
          beacon_number[i]=beacon_number[tmp]+1;
        }
      }
    front++;
  }
}


  int main(void)
  {
   
    
    int n,m,min=100000,result;
    scanf("%d %d",&n,&m);
    int store[n+1]; //베이컨 수 저장
    for(int i=1;i<=m;i++) //인전행렬에 저장
      {
        int tmp1,tmp2;
        scanf("%d %d",&tmp1,&tmp2);
        arr[tmp1][tmp2]=1;
        arr[tmp2][tmp1]=1;
      }

    for(int j=1;j<=n;j++)
      {
        int cnt=1;
        int front=1,rear=1;
        for(int i=1;i<=n;i++)
          {
            if(arr[j][i]==1)
            {
              queue[rear++]=i;
              beacon_number[i]=1;
            }
          }
        bfs(front,rear,cnt++,n); //나머지 인접행렬을 bfs를 이용해 구함!
        
        int add=0;
        for(int i=1;i<=n;i++)
          {
            if(i==j)
              continue;
            add+=beacon_number[i];
          }
       // printf("%d: %d 후후후\n",j,add);
        if(add<min)
        {
          min=add;     
          result=j;
        }
          
        clear(); //queue,beacon_number 초기화
      }

    printf("%d",result);
    
  }