(백준 알고리즘 문제풀이) 1325번 효율적인 해킹
by 줌코딩
문제
어떻게 접근할 것인가
- 하나의 점에서 시작해서 접근할 수 있는 모든 점의 수를 저장하고
- 가장 큰 점들을 프린트 한다.
코드
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int m, n, v, w, M;
vector<vector<int> > ll;
int bfs(int s){
int c = 0;
queue<int> q;
q.push(s);
vector<int> visited = vector<int>(n+1, 0);
visited[s] = 1;
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = 0; i < ll[x].size(); i++){
int y = ll[x][i];
if(visited[y])continue;
visited[y] = 1;
q.push(y);
c++;
}
}
return c;
}
int main(){
scanf("%d %d", &n, &m);
ll = vector<vector<int> >(n+1);
vector<int> trust(n+1);
for(int i = 0 ; i < m; i++){
scanf("%d %d", &v, &w);
ll[w].push_back(v);
}
for(int i = 1; i < n + 1; i++){
trust[i] = bfs(i);
if(trust[i] > M) M = trust[i];
}
for(int i = 1; i < n + 1; i++){
if(trust[i] == M) printf("%d ", i);
}
}
느낀점
- BFS는 뚝딱뚝딱!
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Subscribe via RSS