알고리즘 문제
[C/C++ 백준 1058번] 친구 (Silver 2)
새파란 공대생
2020. 9. 30. 00:01
1058번: 친구
지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람�
www.acmicpc.net
어려운 개념은 아닌데, 구현이 정말 짜증나는 문제였다.
bfs와 depth 개념을 이용해 풀었다. 문제의 개념대로 모든 점에 대해 거리 2이내의 점들의 개수를 구해, 최댓값을 출력해주는 문제이다. 질문을 보니 워셜 플로이드 알고리즘을 많이 사용하던데, 내일 한번 봐야겠다.
## dfs로는 풀기 어려워보인다. 한번 탐색을 진행할 때 true로 바꿔버리기 때문. 물론 새 탐색을 진행할 때마다 초기화 할수는 있겠지만, bfs가 좀 더 직관적이다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int bfs(vector <int> graph[], int friends[], int N, int n){
queue <int> q;
int ans = 0;
bool visit[N];
int depth[N];
for(int i=0; i<N; i++)
visit[i] = false;
q.push(n);
visit[n] = true;
depth[n] = 0;
while(!q.empty()){
int tmp = q.front();
q.pop();
for(int i=0; i<graph[tmp].size(); i++){
if(visit[graph[tmp][i]]==false){
depth[graph[tmp][i]]=(depth[tmp]+1);
visit[graph[tmp][i]]=true;
if(depth[graph[tmp][i]]<=2)
ans++;
q.push(graph[tmp][i]);
}
}
}
return ans;
}
int main(void){
int N, maxi = -1;
char x;
scanf("%d", &N);
vector <int> graph[N];
int friends[N];
for(int i=0; i<N; i++){
friends[i] = 0;
for(int j=0; j<N; j++){
scanf(" %c", &x);
if(i>j){
if(x=='Y'){
graph[i].push_back(j);
graph[j].push_back(i);
}
}
}
}
for(int i=0; i<N; i++){
maxi = max(maxi, bfs(graph, friends, N, i));
}
printf("%d", maxi);
}