[BOJ]1389 케빈 베이컨의 6단계 법칙(S1, C++)

📋 개요 

잠깐 건강 이슈와 취준 이슈로 포스팅을 쉬었다. 하지만 알고리즘 문제는 꾸준히 풀었고 풀면서 복기하고 다시 문제를 되돌아보는것이 중요하다고 느꼈다. 포스팅을 꾸준히 이어나갈 예정이다.

 

기술적인 고민보다는 Raw하게 개발과 CS를 더 집중한다.

 

---

🧩 문제

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

📝  형식 

📥 입력	📤 출력
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.	첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1	5 5 1 3 1 4 4 5 4 3 3 2	3

 

🥕  내 코드 및 정답코드

---

📖  해설 및 느낀점

#해설

우리가 아는 케빈 베이컨이론이다. 6다리만 건너면 아는 사람이 있다. 모든 사람은 연결되어있다. 뭐 이런 법칙이다.

여기서 누가 가장 다리를 덜 건너고 아는 사람을 마주칠 수 있을까? 가 이 문제의 핵심이다.

 

" 누가 가장 다리를 덜 건너고"는 최단거리의 문제이다. 최단거리의 문제는 BFS를 활용하여 풀어낼 수 있다.

1번이 2번,3번,4번,5번을 만날때 나오는 다리 갯수의 합과 2번이 1번,3번,4번,5번을 만날때 나오는 다리 갯수의 합을 다 구해서 1~5번까지 다리의 총합 갯수가 가장 적은 사람을 찾는 문제이다.

 

즉, 이 문제는 BFS의 변형이라고 볼 수 있다. BFS만 안다고 해서 절대로 풀어 낼 수가 없다. 이를 응용할 줄 알아야한다.

 

bfs를 응용하여 dist[]의 값을 구할 수 있다.

int dist[101]; //방문노드 대신 distance 배열 선언

int bfs(int start){
    queue<int> q;
    q.push(start);
    memset(dist, -1, sizeof(dist)); //순회할때마다 초기화
    dist[start] = 0;
    while(!q.empty()){
        int current = q.front();
        q.pop();
        
        for(int i = 0 ; i < graph[current].size(); i++){
            int next = graph[current][i];
            if(dist[next] != -1) continue; //지나쳤다면 -1이 아니기 때문에
            dist[next] = dist[current] +1; //한다리 건널때마다 +1을 해줌
            q.push(next);
        }    
    }
    int cnt =0;
	for (int i = 1; i <= N;i++) {
		cnt += dist[i]; //distance에 있는 총합을 더한다.
        /*
        0 2 1 1 2 
	2 0 1 2 3 
	1 1 0 1 2 
	1 2 1 0 1 
	2 3 2 1 0 
        */
	}
	//cout << cnt;
    return cnt;
}

 

인접 행렬을 만드는 것도 중요한데, 아래와 같은 방식으로 만들면 된다.

    for(int i =0 ; i <  M ;i++){
        int s,e;
        cin >>s>>e;
        
        graph[s].push_back(e);
        graph[e].push_back(s);
    }

 

자주 사용을 해야 안까먹는데 까먹어서... 기억하기 위해 남겨두었다.

 

#문법

이번에 사용한 C++의 새로운 문법은 memset();이다. 이걸 사용하려한 이유는 삼성전자 코테 풀이에 매우 유용하다고 했기 때문에 이다. 배열이나, vector를 초기화하는 방법은 너무 많지만, 훈련을 위해 memset을 사용했다. 나름 코드도 깔끔해지고 나쁘지 않은 것 같다. 일반 pc환경에서는 memset이 좋다고는 하는데 한정적인 자원을 사용하는 임베딩 시스템에서는 잘 모르겠다.

#include <cstring> //memset을 위한 헤더

int main(){
	
    int arr[101] = {0, };
    //memset(배열, 값, 배열의 크기); 
    memset(arr, -1, sizeof(arr));
    
	return 0;
}

 

#느낀점

코드 구현하는게 어려운거 같다. 아직 익숙하지 않아서 인가.... 뭔가 이렇게 해야지 하고 작성하면 귀찮은건지 모르는건지... 생각을 하기가 싫어진다.. 마음을 다잡고 공부해야한다.