[백준(BOJ)] 1325번 효율적인 해킹 C++

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

1325번: 효율적인 해킹

 

어떤 문제인가?

문제를 읽어보면 위 문제의 그래프는 단방향 그래프이다.

 

A컴퓨터가 B컴퓨터를 신뢰한다는 뜻은 

B정점이 A정점을 가리키고 있다는 것이다.

 

이 점을 생각하고 어떠한 정점이 연결된 정점들의 개수가 가장 많은 정점들을 출력하면 된다.

 

접근 방법

 

vector<int> graph[10001];
bool visited[10001];

정점을 저장할 벡터와 방문 여부를 저장할 배열을 선언해준다.

 

 

int n, m;
cin >> n >> m;

문제에서 주어진 변수를 선언하고 입력받는다.

 

 

while (m--) {
    int a, b;
    cin >> a >> b;
    graph[b].push_back(a);
}

간선의 개수인 m번만큼 한 간선이 연결하는 두 정점을 입력받는다.

 

이때, 단방향 그래프임에 유의하여 b정점에 연결된 정점으로 a를 추가해준다.

 

 

int maxNum = 0;
vector<int>ans;

for (int i = 1; i <= n; i++) {

    int cnt = dfs(i);

    if(cnt > maxNum){
        maxNum=cnt;
        ans.clear();
        ans.push_back(i);
    }
    else if(cnt ==maxNum){
        ans.push_back(i);
    }

    for (int j = 0; j <= n; j++) {
        visited[j] = false;
    }
}

int dfs(int x) {
    int cnt = 0;
    visited[x] = true;

    for (int i: graph[x]) {
        if (!visited[i]) {
            cnt++;
            cnt += dfs(i);
        }
    }
    return cnt;
}

연결된 정점들의 최대 개수를 저장할 maxNum과 그 정점들을 저장할 벡터를 선언해준다.

이제 반복문을 돌며 모든 정점들을 살펴볼 것이다.

 

여기서, dfs함수는 연결된 정점들의 개수를 반환해주는 것이다.

연결된 정점들의 개수는 곧 dfs함수가 호출된 횟수이다.

 

cnt에 i번 정점을 dfs 한 결과를 저장한다.

이때 maxNum과 비교하여 다른 연산을 진행한다.

 

1. 기존의 maxNum보다 cnt가 큰 경우

당연히 maxNum을 cnt로 바꿔준다.

이 경우 이전에 벡터에 있던 정점들의 번호가 정답이 아니므로 ans 벡터를 비워준다.

그리고 비워진 벡터에 i 정점을 추가해준다.

 

2. 기존의 maxNum과 cnt가 같은 경우

이 경우에는 벡터에 i 정점을 추가만 해주면 된다.

 

i 정점에 대한 dfs연산을 했으니 visited배열을 false로 바꿔준다.

반복문이 종료됐다면 ans벡터에 정점들의 번호가 저장되어있을 것이다.

 

for(int a : ans){
    cout << a << " ";
}

출력해주면 끝!

 

 

무엇이 어려웠는가?

문제의 뜻이 단방향 그래프임을 알고,

한 컴퓨터를 해킹했을 때 해킹할 수 있는 다른 컴퓨터의 개수가

각 정점들이 갈 수 있는 정점들의 개수라는 것을 바로 알 수 있었다.

그래서 이 문제는 간단한 구현으로 풀 수 있었다.

 

 

 

전체 코드

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/DFS%EC%99%80%20BFS/1325.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.