[1325] 효율적인 해킹, c++

[1325] 효율적인 해킹

 

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

1325번: 효율적인 해킹

한줄 후기 : 이땐 그래프가 재밌었는데..

 

효율적인 해킹 이 문제도 전형적인 그래프 문제인데 작년에 풀다 실패했었다. 시간초과 나서

그리고 다시 풀어봄. AC 성공

BFS로 풀었다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> com[10001];
int n, m, cnt=0;
void bfs(int start){
	queue<int> q;
	int visit[10001]={0};
	visit[start] = 1;
	q.push(start);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i=0; i<com[x].size(); i++){
			int y = com[x][i];
			if(!visit[y]){
				q.push(y);
				visit[y] = 1;
				cnt++;
			}
		}
	}
}
int main(){
	int arr[10001]={0};
	scanf("%d %d", &n, &m);
	int x, y, max2=0;
	for(int i=0; i<m; i++){
		scanf("%d %d", &x, &y);
		com[y].push_back(x);
	}
	for(int i=1; i<=n; i++){
		if(!com[i].empty()){
			bfs(i);
			arr[i] = cnt;
			cnt = 0;
		}
	}
	for(int i=1; i<=n; i++){
		max2 = max(arr[i], max2);
	}
	for(int i=1; i<=n; i++){
		if(max2 == arr[i])	printf("%d ", i);
	}
	return 0;
}

풀이) 정말 간단하다. A->B 신뢰, B 해킹시 A도 해킹 가능 => 단방향그래프!

반대로 생각해야하기 때문에 입력을 거꾸로 받아줘야 편함.

벡터로 링크드 리스트 구현 후 각각의 정점을 기준으로 BFS 돌면서 cnt개수를 증가시켜 준다. 그 후 기록할 배열에 해킹 할 수 있는 컴퓨터 수를 저장

마지막으로 max 값들의 정점 번호를 순서대로 출력해 주면 된다.

사실 작년에 풀었을 때는 괜히 시간초과 날까봐 cnt를 바로바로 max로 만들어줬었다. 근데 그게 오히려 오래 걸린 듯

​

// 시간초과
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> com[10001];
vector<int> result_cnt;
int num;
long long cnt=0;
void dfs(int n){
	bool visit[10001] = {false};
	for(int i=1; i<=com[n].size(); i++){
		int next = com[n][i-1];
		if(!visit[next]){
			cnt++;
			visit[next] = true;
			dfs(next);
		}
	}
}
int main(){
	int m;
	int x,y, max=-1;
	cin >> num >> m;
	for(int i=0; i<m; i++){
		scanf("%d %d", &x, &y);
		com[y].push_back(x);
	}
	for(int i=1; i<=num; i++){
		if(!com[i].empty()){
			cnt=0;
			dfs(i);
			if(max < cnt){
				result_cnt.clear();
				result_cnt.push_back(i);
				max = cnt;
			}
			else if(max == cnt){
				result_cnt.push_back(i);
			}
		}
	}
	for(int i=0; i< result_cnt.size(); i++){
		cout << result_cnt[i] << " ";
	}
}

보면 result_cnt 벡터에 그때 그때 cnt 맥스 값을 바꿔주느라 더 오래 걸린 것 같음. 답은 제대로 나왔었다.

아무튼 그래도 실패했던 문제 성공해서 기분 좋았음.