문제를 읽자마자 든 생각 : 음~ bfs (최단 거리니까)
별로 수도 안 크니까.. 연결 리스트로 구현하면 뚝딱이겠군.... 하고 생각
실버1 문제 중에서 무작위로 하나 골라서 풀고 있는데... 확실히 유명한 알고리즘들을 배우니까 (dfs bfs, dp, 백트래킹) 그 알고리즘 대로만 구현해도 쉽게 풀리는 문제가 많아서 수월하다... 다만 좀 날먹하는 느낌이 없지않아 있어서 좀 더 어려운 문제를 풀어야 하긴 할 듯 (문제를 막 보고 쓴 코멘트,,, 이 글의 길이를 보면 절대 날먹은 아니었다)
그러면 바로 코드를 짜보자!
연결 리스트를 사용하려 했지만... 중복되는 경우도 존재한다는 조건을 뒤늦게 발견! 갑자기 막혔다
중복을 제거할 수 있는 좋은 방법을 생각해야 한다...
뭔가 함수가 또 있지 않을까... 하는 생각에 구글링을 해봄.
https://www.techiedelight.com/remove-duplicates-vector-cpp/
역시나 함수가 있었다. 다만 시간복잡도가 O(n^2)면... 썩 넉넉한 건 아니기 때문에 막 쓰고 다니기는 곤란하겠다는 생각이 들었음...
일단 이 문제는 시간 제한이 2초고 위에서도 말했듯이 수가 전반적으로 다 크지는 않아서 괜찮을 거라고 생각하고 저 함수를 써봐야겠다고 생각했음.
그리고 또 뻔뻔하지만... 너무 오랜만에 bfs 해봐서 코드 어케 짜는지 다 까먹음 ^_^
그래서 bfs 코드 참고하면서 짰음...ㅎㅎ 이런 건 여러 번 해보면서 익숙해져야 한다고 생각하는 편이라 뭐 문제 없다고 생각함... 풀이만 떠올리면 됐지ㅎㅎ
또 코드를 짜는데 문제가 요구하는 게 bfs만 써서 되는 게 아니라는 걸 뒤늦게 깨달음ㅋㅋㅋㅋㅋ 그냥 bfs는 연결되어 있지 않은 사람한테 가는 데 얼마나 걸리는지 최단 거리를 구할 때만 사용하고... 모든 사람의 케빈 베이컨 수를 구해서 더하는 게 중요한 거구나~ㅋㅋㅋㅋㅋ
이것도 뭐 근데.. 구현이 어려울 것 같지는 않으니 그냥 해보기로 했음...
전체 케빈 베이컨 수라는 게 결국, 모든 숫자에 대해서 탐색한 횟수가 되는 건데, 그러면 부모 노드에서 자식 노드로 들어가는 횟수를 모두 더하면 되는 거 아닌가? 하는 생각이 들었음. 그래서 그렇게 일단은 구현함.
하고 일단 횟수가 잘 구해지는지 테스트만 돌려보려고 했는데 자꾸 에러가 뜨는 거임^^ 그래서 왜 그런지 찾아보니... 벡터 이름을 friend로 했는데 이게 사실 키워드였음ㅋㅋㅋㅋㅋㅋ 눈물의 변수명 변경^
젠장.. 또 이와중에 remove 쓰는 법을 보니까 꽤 귀찮았음... 배열 크기도 자동으로 안 줄어들어서 erase로 또 줄여야 하고... 이것도 그래서 눈물 흘리면서 공부함ㅋㅋㅋㅋ
그래서 이 모든 과정을 걸쳐 제가 구해낸 예제의 케빈 베이컨 수! 공개합니다
0
0
0
0
0오열하기.......
하지만 이유를 찾아야 했다. 그리고 remove를 잘못해서라는 걸 깨달고.. 고쳤음ㅎㅎ
근데 또 위에 말한 것처럼 탐색 횟수로만은 케빈 베이컨 수를 찾을 수 없다는 걸.. 또 깨달음ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 사유 : 여러 개를 거쳐서 간 경우에 중복되는 횟수를 고려 못 함
그래서 이번에는 몇 번 들어갔는지를 횟수에 더하면 구해질 테니까 그렇게 해보려고 했는데... 몇 번 들어갔는지를 구하는 방법이 도저히 떠오르지를 않음....^^ 젠장
결국 다른 분의 글을 참조해 겨우 방법을 구함...
https://hanyeop.tistory.com/113
근데 이쯤되니 시간초과가 뜨는 건 아닐까...하는 불길한 예감을 느낌
그냥 인접 배열로 할껄^^하고 크게 후회하기 시작함
하지만 귀찮아서 어쩔 수 없었음... 일단 제출은 하기로 결심
그리고 시간초과 따위는 없었다! 오히려 0ms 걸림ㅋㅋㅋㅋ 뭐지? 케이스 수가 적어서 그런 듯
결과적으로 정답을 얻은 코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int bfs (vector<vector<int>>& f, int n, int ini) {
queue<int> q;
vector<bool> is_used (n+1, false);
int total_cnt = 0, level_cnt = 1;
bool do_sum = false;
q.push(ini);
is_used[ini] = true;
while (!q.empty()) {
int s = q.size();
for (int i = 0; i < s; i++) {
int node = q.front();
q.pop();
for (int j = 0; j < f[node].size(); j++) {
if (!is_used[f[node][j]]) {
is_used[f[node][j]] = true;
q.push(f[node][j]);
total_cnt += level_cnt;
}
}
}
level_cnt++;
}
return total_cnt;
}
int main() {
ios_base :: sync_with_stdio;
cin.tie(NULL);
cout.tie(NULL);
int n, m, min_kevin = 100*100, min_person = 0;
vector<vector<int>> f;
cin >> n >> m;
f.assign(n+1, vector<int>(0));
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
f[a].push_back(b);
f[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
auto end = f[i].end(); // end iterator에 f[i].end() 대입
for (auto iter = f[i].begin(); iter != f[i].end(); iter++) {
end = remove(iter + 1, end, *iter); // 지워지지 않은 마지막 원소 바로 뒤의 반복자를 리턴
}
f[i].erase(end, f[i].end()); //배열이 차 있는 범위 바로 다음부터 배열 끝까지 지우기
}
for (int i = 1; i <= n; i++) {
int kevin = 0;
kevin = bfs(f, n, i);
if (kevin < min_kevin) {
min_kevin = kevin;
min_person = i;
}
}
cout << min_person;
}그래서 이번에 배운 건
1. remove와 erase 함수의 사용법
2. bfs의 level을 구하는 법
3. c++에서 friend는 키워드! (다른 클래스를 friend로 지정해서, private인 필드나 메소드에 접근할 수 있도록 하는 키워드라고 함)
그리고 느낀 점은
1. 이게 무슨 알고리즘을 써서 푸는 문제다! 라고 바로 알아차리는 건 좋은데 그래서 그 알고리즘을 어떻게 사용해서 결과적으로 무슨 답을 얻을 건지를 생각해야 함. 지금이야 쉬운 문제를 풀어서 단순히 알고리즘을 적용하기만 해도 답이 나오지만 나중에는 그러지 않을 것이기 때문에...
2. 이정도로는 시간 초과 안 나는구나...
아무튼 이렇게 해서 끝!
