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

📕문제

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

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

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

📕입력

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

📕출력

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

---

🔎문제 해석

---

처음 문제를 보고 살짝 헷갈린 부분이 있었습니다.

문제에서의 신뢰관계를 저는 화살표로 표현해보겠습니다.

3->1
3->2
4->3
5->3

이 화살표의 의미는 화살표의 도착지에 해당하는 컴퓨터를 해킹하면 출발지를 해킹할 수 있다는 뜻입니다.

즉, 1번 컴퓨터를 해킹하면 3번과 3번을 도착지로 하는 출발지인 4,5번을 해킹할 수 있습니다.

이런식으로 계산을 하면

• 1번은 1번을 포함한 4개의 컴퓨터 [1,3,4,5]
• 2번은 2번을 포함한 4개의 컴퓨터 [2,3,4,5]
• 3번은 3번을 포함한 3개의 컴퓨터 [3,4,5]
• 4번은 4번을 포함한 1개의 컴퓨터 [4]
• 5번은 5번을 포함한 1개의 컴퓨터 [5]

이라는 결과가 나오게 됩니다.

이제 이것을 코드로 바꾸기만 하면 됩니다.

 

저는 dfs를 사용해서 도착 지점인 번호에 해당하는 컴퓨터의 해킹 가능한 컴퓨터 수를 늘려줬습니다.

그리고 최대값을 계속해서 검사해줬습니다. [나중에 최댓값에 해당하는 컴퓨터를 출력하기 위함]

 

 

💻코드

---

/*
실버 1 효율적힌 해킹 dfs bfs
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, c = 0, Max = 0;
vector<int> graph[10001];
void dfs(int v);
vector<int> visit;
vector<int> vertex;
int main()
{
    int start, finish;
    cin >> n >> m;
    vertex.resize(n + 1);
    for (int i = 0; i < m; i++)
    { //간선 입력
        cin >> start >> finish;
        graph[start].push_back(finish);
    }
    for (int i = 1; i <= n; i++)
    {
        visit = vector<int>(n + 1, 0);
        visit[i]++;
        dfs(i);
    }
    for (int i = 1; i <= n; i++)
    {
        if (vertex[i] == Max)
        {
            cout << i << " ";
        }
    }
}
void dfs(int v)
{
    vertex[v]++;
    Max = max(Max, vertex[v]);
    for (int i = 0; i < graph[v].size(); i++)
    {
        int next = graph[v][i];
        cout << v << " " << next << endl;
        if (!visit[next]) //첫 방문.
        {
            visit[next]++;
            dfs(next);
        }
    }
}

 

✔느낀점

• 굉장히 오랜만에 알고리즘을 풀어봤는데 역시 알고리즘은 꾸준한 연습이 필요한 것 같습니다.
• 메모리 초과가 굉장히 많이 떴었는데,, 해결하니 굉장히 사소한 문제여서 허탈했습니다...
• 시간 초과와 메모리 초과가 굉장히 많이 떴었던 문제,,
• vector <int> graph [n] 이러한 선언방식을 처음 써봤는데 생각보다 유용했습니다.
  • 2차원 배열보다 훨씬 효율적인 거 같습니다. n*n 보다 내가 원하는 만큼만 만들 수 있다는 점이 좋았습니다.