[백준 1325] 효율적인 해킹

문제설명

 

이 문제는 연결관계를 파악하여 해킹 가능한 컴퓨터가 많은 컴퓨터를 출력한다

만약 그 갯수가 동일하다면, 컴퓨터의 번호를 오름차순으로 출력한다

알고리즘

1. 컴퓨터의 수와 간선의 관계를 입력받는다

2. 간선의 관계는 단방향으로 저장한다(b가 해킹되면 a도 가능하다)

3. bfs 함수에서 각 컴퓨터가 해킹가능한 컴퓨터의 수를 센다

4. 컴퓨터의 수와 컴퓨터 번호를 저장한다

5. 정렬을 통해 해킹 할 수 있는 컴퓨터의 수가 가장 많은것, 그리고 인덱스는 오름차순으로 정렬한다

6. 첫 값은 무조건 가장 크기때문에 이와 같은 값인 컴퓨터의 인덱스를 모두 출력한다

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


vector<int> graph[10001];
bool visited[100001];
bool cmp(pair<int,int> x, pair<int,int>y) {
	if (x.first > y.first)//해킹 가능 컴퓨터 수 오름차순 정렬
		return true;
	else if (x.first == y.first)//컴퓨터 수가 같을 경우 컴퓨터 번호 내림차순
		return x.second < y.second;
	else
		return false;
}
int bfs(int x) {
	
	queue<int> q;
	int cnt = 0;
	q.push(x);
	visited[x] = true;
		while (!q.empty()) {

			int current = q.front();
			q.pop();

			for (int i = 0; i < graph[current].size(); i++)
			{
				int next = graph[current][i];
				if (visited[next] == 0) {//방문한 적 없는 것 만 방문
					q.push(next);
					visited[next] = true;
					cnt++;
				}
				
			}
		}
		return cnt; //해킹 가능한 컴퓨터 수 반환
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	vector<pair<int,int>> answer;//해킹가능 컴퓨터 수를 저장하는 벡터
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[b].push_back(a); //단방향으로만 연결 !!!!!! b가 a를 해킹가능 
	}
	for (int i = 0; i < N; i++) 
	{
		int result = bfs(i + 1);
		answer.push_back({ result, i + 1 }); //해킹가능 컴퓨터 수, 컴퓨터 번호
		fill(visited, visited + 100001, 0);//방문 초기화
	}
	sort(answer.begin(), answer.end(), cmp); //정렬

	int max = answer[0].first;
	for (int i = 0; i < answer.size(); i++)
	{
		if (answer[i].first == max)
			cout << answer[i].second <<" ";
	}
	
}

고찰

이번문제는 값은 제대로 나왔는데 제출 시 알 수 없는 오류를 겪었다

출력 오류가 있었는데 배열 최대값을 변경하니까 해결되었다

정확하게 무슨 문제인지 알 수 없었다

 

bfs알고리즘을 사용하여 문제를 풀면 되는데, 다른 문제들과 가장 다른점은 바로 간선이 양방향으로 연결되어 있지 않는 점이다

문제를 잘 읽어보면 a b 관계로 입력 되어 오면 b를 해킹하면 a도 가능하다 라고 되어있다

따라서 a b를 입력 받았을 때 양방향이 아닌 b a 순으로만 저장한다

그리고 각 컴퓨터 마다 접근 가능한 컴퓨터의 수를 센다음에 최대인 값을 구하고 그 컴퓨터번호를 출력시키는 문제였다