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

1325. 효율적인 해킹
문제 풀이

1325번: 효율적인 해킹

 

DFS로 풀자고 생각한 문제!

 

DFS는 그렇다 치고... 10000 * 10000의 인접 행렬로 구현하려고 했지만... 메모리를 너무 많이 쓰는 것도 같고 탐색할 때 시간이 오래 걸릴 것 같아서 vector의 배열로 만들어주었다.

 

신뢰하는 컴퓨터의 번호만 넣어주는 vector이다.

 

알고리즘 설계

1. A와 B 컴퓨터를 받을 때, B번째 vector에 A를 넣어준다. ( B가 신뢰하는 컴퓨터가 A라는 뜻 )
2. 1번부터 컴퓨터의 수까지 DFS를 돌린다.
3. vector에 있는 노드를 방문하지 않았다면, count를 1씩 늘리고 다시 그 노드의 컴퓨터 번호가 신뢰하는, 즉 연결되어있는 노드들을 탐색해준다.
4. DFS 함수는 연결되어있는 모든 노드들을 탐색한 후 해킹한 컴퓨터 수를 반환한다.
5. 최댓값을 뽑아내어 해당 컴퓨터 번호들을 배열로 묶고 출력한다.

 

알고리즘 설계를 제대로 쓰지 못한 것 같은데... 코드를 보면 바로 이해가 된다.

 

코드

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

vector<int> maxes;
vector<int> m[10001];
bool visited[10001];

int DFS(int n)
{
    int count = 0;
    visited[n] = true;

    for (int i = 0; i < m[n].size(); i++)
    {
        int node = m[n][i];

        // 해킹하지 않은 곳만 방문
        // 해킹할 때마다 count를 올린다
        if (!visited[node])
        {
            count += DFS(node);
            count++;
        }
    }

    // 최종 해킹 횟수 반환
    return count;
}

int main()
{
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    int cnt, len, maxValue = 0;
    cin >> cnt >> len;

    for (int i = 0; i < len; i++)
    {
        int a, b;
        cin >> a >> b;

        m[b].push_back(a);
    }

    for (int i = 1; i <= cnt; i++)
    {
        int temp = DFS(i);

        if (maxValue <= temp)
        {
            // 최댓값 구하기
            if (maxValue < temp)
            {
                maxValue = temp;
                maxes.clear();
            }

            // 최대 배열에 넣는다
            maxes.push_back(i);
        }

        fill_n(visited, 10001, false);
    }

    for (int i : maxes)
        cout << i << ' ';
}

결과는 성공이었지만!!

 

아무래도 비효율적인 것 같아서... 메모이제이션을 이용해서 구현해보았다.

 

void DFS(int n)
{
    visited[n] = true;

    for (int i = 0; i < m[n].size(); i++)
    {
        int node = m[n][i];

        if (!visited[node])
        {
            if (memo[node] == 0)
            {
                DFS(node);
                temp++;
            }
            else
            {
                temp += memo[node];
            }
        }
    }

    if (memo[n] != 0)
        memo[n] = temp;
}

 

결과는 더 느려졌다... 왜일까...??

 

아무튼 더 좋은 코드를 위해서 맞았지만 계속 노력해서 뿌듯했다. 재밌는 문제!