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

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

 

그동안 삼성 개빡구현 문제를 훈련해서 그런지,, 실버문제는 그냥 풀려버린다.

 

익숙한 알고리즘이라 그런건가?

뭔가 그래도 꽤 잘 풀린 느낌이었다.

1. 문제 해석

    // n개의 컴퓨터
    // 한 번의 해킹 -> 여러 개의 컴퓨터를 해킹할 수 있는 컴퓨터 해킹
    // a가 b신뢰 : b를 해킹카면 a도 해킹 가능
    // 신뢰 관계 주어졌을 때, 가장 많은 컴퓨터 해킹할 수 잇는 컴퓨터 번호 출력

 

여기서 주의할 점은 신뢰 관계이다.
이 관계가 일반적인 문제와는 반대로 되어있기 때문에 조건을 잘 파악하고 문제풀이에 들어가는 것이 중요하다.

 

2. 문제 풀이

이런 그래프 문제들은 전역으로 필요한 변수들을 두는게 문제 풀이에 편하다.

함수 인자로 두는 방법이 더 효율적인지 뭔지는 모르겠지만,, 일단 아래와같이 풀었다.
오늘 알고리즘 스터디에서 새로운 방법에 대해 고민해보는 시간을 가져봐야겠다.

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

vector<int> computer(10001);
vector<vector<int>> graph(10001);
int cnt;
void dfs(int node, vector<bool> &is_visited)
{
    cnt++;
    // cout << "node << " << node << " depth : " << cnt << endl;
    // 이미 방문했다면 멈추기
    if (is_visited[node])
    {
        return;
    }

    is_visited[node] = true;
    // computer[node] = cnt; // 깊이 적용

    for (auto com : graph[node])
    {
        if (!is_visited[com])
        {
            dfs(com, is_visited);
            // is_visited[com] = true;
        }
    }

    // return cnt;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    // n개의 컴퓨터
    // 한 번의 해킹 -> 여러 개의 컴퓨터를 해킹할 수 있는 컴퓨터 해킹
    // a가 b신뢰 : b를 해킹카면 a도 해킹 가능
    // 신뢰 관계 주어졌을 때, 가장 많은 컴퓨터 해킹할 수 잇는 컴퓨터 번호 출력

    int n, m;

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
    {
        vector<bool> is_visited(n + 1, false);
        cnt = 0;
        dfs(i, is_visited);
        computer[i] = cnt;
    }
    vector<int> ans;
    int max_search = -1;

    for (int i = 1; i <= n; i++)
    {
        if (max_search < computer[i])
        {
            max_search = computer[i];

            ans.clear();      // 비우고
            ans.push_back(i); // 추가
        }
        else if (max_search == computer[i])
        {
            ans.push_back(i);
        }
    }

    for (auto e : ans)
    {
        cout << e << " ";
    }
}