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

www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

처음에 문제 접했을 때 정답률이 엄청 낮길래 '뭔가 있는게 분명하다'라고 생각하며 풀었다. 하하 근데 bfs로 쉽게 풀 수있는 문제였다..뭔가 속은기분..ㅎㅅㅎ

 

문제에서는 "A가 B를 신뢰하는 경우 B를 해킹하면, A도 해킹할 수 있다"라는 문장이 있다. 다른 문제같았으면 2차원 배열에 A와 B를 모두 check해주어 서로 연결됨을 알려주었겠지만, 이 문제에서는 B를 통해 A를 해킹할 수 있다는 것을 알려주기 위해 2차원 vector에 다른 방식으로 저장해주는 작업을 거쳤다.

 

  for (int i = 0; i < M; i++)
    {
        cin >> a >> b;
        computers[b].push_back(a); //b를 해킹하면 a를 해킹할 수 있습니다! 아하하
    }

 

엄청 특별한 작업은 아니었고, 둘의 위치를 바꾸어 주는 것이다,, 지금까지 거쳐온 문제들은 a와 연결된 노드 b,,이런 식의 접근으로 저장해주었겠지만, 이 문제에서는 b가 해킹할 수 있는 것들을 저장해주는 것이 훨씬 문제를 푸는데에 쉬울 것이라고 판단하였다.

 

후에는 뭐 여느 bfs문제와 같이 visited와 vector의 방문을 통해 문제의 "해커 김지민"씨가 한번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 개수를 count했다.이 중 가장 max값을 따로 저장해두었고, 현재 i에서 시작하였을때 몇개의 count가 세어지는지를 result vector에 저장해주었다. 마지막에는 result를 sorting하고, (pair라면 자동으로 first값으로 sort됨) max의 값을 가진 아이들을 출력해주면된다.

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> computers(100001);
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M, max_c = 0;
    vector<pair<int, int>> result;
    cin >> N >> M;
    int a, b;
    for (int i = 0; i < M; i++)
    {
        cin >> a >> b;
        computers[b].push_back(a); //b를 해킹하면 a를 해킹할 수 있습니다! 아하하
    }

    for (int i = 1; i <= N; i++)
    {
        bool visited[100001] = {
            false,
        };
        int count = 0;
        queue<int> q;
        q.push(i);

        while (!q.empty())
        {
            int com = q.front();
            q.pop();
            visited[com] = true;

            for (int j = 0; j < computers[com].size(); j++)
            { //해당 컴퓨터가 해킹할 수 있는 것들 queue에 추가
                int ncom = computers[com][j];
                if (visited[ncom])
                    continue;
                q.push(ncom);
                visited[ncom] = true;
                count++;
            }
        }
        max_c = max(count, max_c);
        result.push_back(make_pair(i, count));
    }

    sort(result.begin(), result.end());
    for (int i = 0; i < result.size(); i++)
    {
        if (result[i].second == max_c)
            cout << result[i].first << " ";
    }

    return 0;
}