알고리즘 :: 백준 :: 1325 - 효율적인 해킹

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• N개의 컴퓨터 ≤ 10,000, M개의 관계도 ≤ 100,000
• 컴퓨터 번호는 1번부터 N번
• 한 번에 가장 많이 해킹할 수 있는 컴퓨터 번호를 오름차순으로 (하나면 한개, 두 개 이상이면 오름차순으로)

✏️ 문제풀이

트리도 그래프의 일종임을 생각하면 어렵지 않게 접근법을 생각할 수 있습니다.

 

입력으로 들어오는 A, B는 'A가 B를 신뢰한다' = 'B를 해킹하면 A도 해킹할 수 있다' = B → A로 생각할 수 있습니다. 즉, 문제에서 말하는바와는 반대방향으로 간선이 만들어지는 겁니다. A가 B를 신뢰하지만, 간선은 B에서 A를 향하도록 만들어집니다

 

이렇게 간선을 이어서 트리를 형성했을 때, 한 번에 가장 많이 해킹할 수 있는 컴퓨터란, 해당 노드를 시점으로 DFS를 진행했을 때 가장 많은 노드를 탐색할 수 있는 경우를 의미합니다.

• 최대 컴퓨터 개수 N = 10,000이고, 트리가 skew tree일 때 매 DFS마다 n번 탐색합니다.
• 최악의 경우 1만 ×1만 = 1억 번 탐색해야 하는데, 시간제한이 5초이므로 이 방법으로 풀 수 있습니다.

[주의사항]

DFS로 그래프를 탐색할 때는 방문표시 잘 해왔지만, 트리를 탐색할 때는 방문표시를 해야 한다는 걸 까먹는 경우가 있습니다. 꼭 검사한 컴퓨터에 대해서는 방문표시를 잊지말고 합시다. 만일 A와 B가 서로 신뢰할 경우, 방문표시를 하지 않을 경우 무한루프 돕니다.

📝 코드

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

int N, M;
vector<uint8_t> visited;
vector<vector<int>> vec;

int dfs(int num) {
	int ret = 1;
	visited[num] = true;    // 사이클 방지하기 위해
	for (int i : vec[num])
		if (!visited[i]) ret += dfs(i);
	return ret;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> N >> M;
	vec.resize(N + 1);
	visited.resize(N + 1);
	
	for (int i = 0; i < M; ++i) {
		int s, e;
		cin >> s >> e;
		vec[e].push_back(s);
	}
	int maxAns = 0;
	vector<int> ans(N + 1);
	for (int i = 1; i <= N; ++i) {
		ans[i] = dfs(i);
		maxAns = max(maxAns, ans[i]);
		fill(begin(visited), end(visited), false);
	}
	for (int i = 1; i <= N; ++i)
		if (maxAns == ans[i]) cout << i << ' ';
}

 

🔗 코드 링크

🕧 결과