[백준] 1325번: 효율적인 해킹 - C++

문제

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

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

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

 

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

 

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

---

그래프 탐색 문제

DFS를 이용하여 풀었다.

 

그래프탐색 이외에 생각해줘야할 것들이 있어 조금 까다로웠던 문제.....근데 그냥 내가 삽질을 많이 해서 어렵게 느껴졌던거다ㅜ

 

기본적으로 신뢰 가능한 컴퓨터끼리 묶어 그래프를 만들어주고, 그래프 탐색을 통해 해킹할 수 있는 컴퓨터의 수를 세어 해당 컴퓨터를 해킹했을 때 몇 대를 해킹할 수 있는지를 담는 배열에 저장한다. 그 뒤 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력해주면 끝이다.

 

그래서 단순히 DFS만 멀쩡하게 구현 가능하면 사실 간단하게 풀 수 있는데,,

시간/메모리 제한으로 인해 고려해야될 부분들 때문에 정답까지 오래걸렸던 것 같다..

 

코드

#include <cstdio>
#include <vector>
#include <cstring>
#define MAX 10001

using namespace std;

int N, M;
int maximum, cnt;

vector<int> computer[MAX];
int counter[MAX];
bool visited[MAX];

void DFS(int num, int start);

int main(void) {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < M; i++) {
        int num1, num2;
        scanf("%d %d", &num1, &num2);

        computer[num2].push_back(num1);
    }

    for(int i = 1; i <= N; i++) {
        memset(visited, false, N + 1);
        cnt = 0;
        DFS(i, i);
        maximum = (counter[i] > maximum ? counter[i] : maximum);
    }

    for(int i = 1; i <= N; i++) {
        if(counter[i] == maximum)
            printf("%d ", i);
    }
    printf("\n");
    return 0;
}

void DFS(int num, int start) {
    visited[num] = true;
    int len = computer[num].size();

    for(int i = 0; i < len; i++) {
        int next = computer[num][i];

        if(!visited[next]) {
            cnt++;
            DFS(next, start);
        }
    }

    counter[start] = (counter[start] > cnt ? counter[start] : cnt);
}