이번에는 백준 1325번 효율적인 해킹 문제를 풀어보았습니다.
이 문제는 한 번 해킹했을 때 가장 많은 컴퓨터를 함께 해킹할 수 있는 시작점을 찾는 문제입니다.
핵심은 입력으로 주어지는 신뢰 관계를 그대로 쓰는 것이 아니라, 실제로 해킹이 전파되는 방향으로 관계를 뒤집어서 저장하는 것이었습니다.
문제 설명
회사에는 N개의 컴퓨터가 있고, 컴퓨터끼리 신뢰 관계가 있습니다.
입력에서 A B가 주어지면,
이는 A가 B를 신뢰한다는 뜻입니다.
문제에서 중요한 해석은 다음입니다.
- A가 B를 신뢰하면
- B를 해킹했을 때 A도 해킹할 수 있다
즉, 입력 방향 그대로가 아니라
실제 해킹 전파 방향은 B → A가 됩니다.
이때 한 번 해킹으로 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 모두 출력하면 됩니다.
풀이 아이디어
이 문제는 각 컴퓨터를 시작점으로 DFS를 돌려서,
도달 가능한 컴퓨터 수를 세면 됩니다.
다만 입력이 A가 B를 신뢰한다 형태이기 때문에,
그래프를 그대로 저장하면 탐색 방향이 맞지 않습니다.
그래서 코드에서는
relation[B].push_back(A);형태로 저장해서,
실제로 해킹이 퍼지는 방향대로 인접 리스트를 만들었습니다.
이후 1번부터 N번까지 모든 컴퓨터를 시작점으로 DFS를 돌리고,
각 시작점에서 도달 가능한 컴퓨터 수를 구한 뒤 최댓값을 비교했습니다.
최대 개수가 여러 개일 수 있으므로,
그 경우를 위해 결과를 저장하는 ret 벡터도 함께 사용했습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
int visited[10000];
vector<vector<int>> relation;
int N,M;
int max_cnt = -1;
vector<int> ret;
int dfs(int here) {
visited[here] = 1;
int ret = 1;
for (int i : relation[here]) {
if (visited[i]) continue;
ret += dfs(i);
}
return ret;
}
int main() {
cin >> N >> M;
relation = vector<vector<int>>(N+1);
for (int i = 0; i < M; i++) {
int A,B;
cin >> A >> B;
relation[B].push_back(A);
}
for (int i = 1; i <= N; i++) {
fill(visited, visited + N + 1, 0);
int cnt = dfs(i);
if (cnt > max_cnt) {
ret.clear();
max_cnt = cnt;
ret.push_back(i);
} else if (cnt == max_cnt) {
ret.push_back(i);
}
}
for (int i : ret) {
cout << i << " ";
}
return 0;
}풀이 흐름
N,M을 입력받는다.- 신뢰 관계를 입력받아 해킹 전파 방향대로
relation에 저장한다. - 1번부터 N번까지 모든 컴퓨터를 시작점으로 DFS를 수행한다.
- 각 DFS 결과로 도달 가능한 컴퓨터 수를 구한다.
- 현재 최대 개수보다 크면 결과 벡터를 비우고 현재 컴퓨터를 넣는다.
- 현재 최대 개수와 같으면 결과 벡터에 추가한다.
- 마지막에 결과 벡터를 출력한다.
구현 포인트
1. 신뢰 관계를 뒤집어서 저장
이 문제에서 가장 중요한 부분은 관계를 저장하는 방향입니다.
입력은 A B, 즉 A가 B를 신뢰한다는 뜻이지만,
실제로는 B를 해킹하면 A를 해킹할 수 있다는 의미입니다.
그래서 코드에서는 다음처럼 저장했습니다.
relation[B].push_back(A);즉, 탐색할 때는 “현재 컴퓨터를 해킹했을 때 다음으로 해킹 가능한 컴퓨터들”이 나오도록 방향을 뒤집은 것입니다.
2. DFS는 현재 컴퓨터 포함 개수를 반환
DFS 함수에서는 현재 노드도 해킹 가능한 컴퓨터 수에 포함시키기 때문에,
시작할 때 ret = 1로 두었습니다.
visited[here] = 1;
int ret = 1;이후 인접한 컴퓨터들로 DFS를 계속 돌면서
도달 가능한 컴퓨터 수를 누적해서 더합니다.
for (int i : relation[here]) {
if (visited[i]) continue;
ret += dfs(i);
}즉, 이 DFS는 “현재 컴퓨터에서 시작해서 해킹 가능한 전체 컴퓨터 수”를 반환하는 구조입니다.
3. 매 시작점마다 visited 초기화
모든 컴퓨터를 시작점으로 각각 DFS 해야 하기 때문에,
한 번 탐색이 끝날 때마다 visited를 다시 초기화해야 합니다.
fill(visited, visited + N + 1, 0);이렇게 해야 이전 시작점의 방문 정보가 다음 DFS에 영향을 주지 않습니다.
4. 최댓값 후보를 ret 벡터에 저장
문제에서는 가장 많이 해킹할 수 있는 컴퓨터가 여러 개일 수 있으므로,
최댓값 후보들을 저장할 벡터가 필요합니다.
if (cnt > max_cnt) {
ret.clear();
max_cnt = cnt;
ret.push_back(i);
} else if (cnt == max_cnt) {
ret.push_back(i);
}즉,
- 더 큰 값이 나오면 기존 후보를 버리고 새로 시작
- 같은 값이 나오면 함께 저장
하는 방식입니다.
5. relation은 인접 리스트 형태
컴퓨터 수가 많기 때문에,
관계를 2차원 배열이 아니라 인접 리스트 형태로 저장했습니다.
vector<vector<int>> relation;
relation = vector<vector<int>>(N+1);이 구조를 사용하면 각 컴퓨터에서 연결된 다음 컴퓨터들만 순회하면 되기 때문에,
그래프 탐색 문제에서 자주 사용하는 방식입니다.
