BOJ 1325 효율적인 해킹

📎Problem Link

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

1325번: 효율적인 해킹

 

📋 문제 정리

• 회사에는 N개의 컴퓨터가 있음.
• A 컴퓨터가 B를 신뢰하는 경우, B를 해킹했을 시 A도 해킹할 수 있음.
• 한 번에 가장 많은 컴퓨터를 해킹 할 수 있는 컴퓨터의 번호를 출력하라.
• 첫째 줄에는 컴퓨터의 개수 N, 신뢰 관계 수 M 입력 (N은 10000보다 작거나 같은 자연수, M은 100000보다 작거나 같은 자연수)
• 둘째 줄부터 M 개의 줄에 신뢰하는 관계 입력. A B 형식으로 적었을 경우 A가 B를 신뢰한다는 의미!

📌 예제 1

예제를 그림으로 나타낸 것이다. 예를 들어 3이 1을 신뢰할 수 있다면 1을 해킹할 때 3도 해킹이 가능하다는 의미로 위와 같이 나타내봤다. 그림의 화살표를 따라 가다보면 다음과 같다.

첫 해킹 PC가 1이면 1->3->4/1->3->5로 총 4대의 컴퓨터를 해킹할 수 있다.

첫 해킹 PC가 2이면 2->3->4/2->3->5로 총 4대의 컴퓨터를 해킹할 수 있다.

첫 해킹 PC가 3이면 3->5/3->4로 총 3대의 컴퓨터를 해킹할 수 있고, 첫 해킹 PC가 4 또는 5일 경우에는 추가로 해킹할 수 있는 PC가 없으므로 총 1대의 컴퓨터만 해킹할 수 있다. 그러므로 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호는 1, 2이고, 이를 오름차순으로 출력해야한다.

 

🧐 Idea

• DFS가 실행될 때 마다 해킹한 컴퓨터 수를 count해줘야 함.
• DFS가 리턴되고 이전 DFS 함수로 넘어가더라도 count 값은 유지해야 함.
• count가 최대 값인 노드를 출력하는데, 이 때 최대 값이 노드가 여러개일 경우 오름차순으로 출력해줘야한다.

---

💻 Code

void DFS(int start) {
		visited[start] = true;
		for (int i = 0; i < v[start].size(); i++)
		{
			int next = v[start][i];
			if (!visited[next])
			{
				count++;
				DFS(next);
			}
		}
	}

해킹할 수 있는 컴퓨터를 탐색하는 DFS 함수는 위와 같이 간단하다. 이전에 늘 해왔던 대로 DFS 함수를 실행시키고, 다음 DFS로 넘기기 전에 count++문을 실행한다.

 

int main() {
	Hacker JiminKim;
	int result[10001] = { 0 };
	int max = 0;
	cin >> JiminKim.N >> JiminKim.M;

	for (int i = 0; i < JiminKim.M; i++) {
		int num1, num2;
		cin >> num1 >> num2;

		JiminKim.v[num2].push_back(num1);
	}
	
	for (int i = 1; i <= JiminKim.N; i++) {
		if (!JiminKim.v[i].size()) continue;
		JiminKim.count = 0;
		JiminKim.DFS(i);

		if (max < JiminKim.count) max = JiminKim.count;

		result[i] = JiminKim.count;
		memset(JiminKim.visited, false, sizeof(JiminKim.visited));
	}

	for (int i = 1; i <= JiminKim.N; i++) {
		if (result[i] == max)
			cout << i << " ";
	}
}

DFS 함수를 실행시키는 for문을 살펴보자. 위에서 살펴본 DFS 함수가 종료된 후 main 문으로 다시 돌아왔을 때, 다음 DFS 함수 실행시키는 count를 0으로 초기화해야하는데, 그 전에 현재의 max 값과 현재 DFS 함수로 부터 계산된 count 값 중 제일 큰 값을 max로 두어, 나중에 모든 노드에 대한 해킹 가능 컴퓨터 수를 훑은 후 count 값이 max 값과 동일한 노드의 번호만 오름차순으로 출력하도록 한다.

 

---