백준 1325 - 효율적인 해킹

문제 설명

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 신뢰 관계를 나타내는 그래프가 주어질 때 하나의 컴퓨터를 해킹하여 최대한 많은 컴퓨터를 해킹할 수 있는 컴퓨터를 구하면 된다.

이때, A가 B를 신뢰하면 B를 해킹했을 때 A도 해킹할 수 있는 것이다.

 

해당 문제는 거꾸로 생각하면 문제를 쉽게 풀 수 있다.

A가 B를 신뢰한다면 A → B로 생각하기 쉽다.

하지만, B를 해킹했을 때 A를 해킹할 수 있기 때문에 화살표를 반대로 하여 DFS나 BFS를 진행하면 된다.

여기서 사이클을 유의해야 한다.

해당 문제의 입력에서는 사이클이 발생할 수 있기 때문에 이를 처리하지 않으면 무한 루프가 발생한다.

이를 방문 여부를 체크하며 사이클을 해결하고 시작 컴퓨터를 기준으로 얼마나 많은 컴퓨터를 방문할 수 있는지 확인하면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<vector<int>> edges;
vector<bool> visited;
int cnt;

void Dfs(int start)
{
	visited[start] = true;
	
	for (auto next : edges[start])
	{
		if (visited[next]) continue;

		cnt++;
		Dfs(next);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	edges.resize(N + 1, vector<int>());
	visited.resize(N + 1, false);

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		edges[b].push_back(a);
	}

	/*
	* b를 해킹하면 a를 해킹할 수 있다.
	*/

	int max = 0;
	vector<int> answers;

	for (int i = 1; i <= N; i++)
	{
		for (int i = 1; i <= N; i++) visited[i] = false;
		cnt = 0;
		Dfs(i);

		if (max < cnt)
		{
			max = cnt;
			answers.clear();
			answers.push_back(i);
		}
		else if (max == cnt)
		{
			answers.push_back(i);
		}
	}

	for (auto ans : answers)
	{
		cout << ans << " ";
	}

	return 0;
}

---