1325 : 효율적인 해킹 - dfs, 인접리스트, 정렬

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

1325번: 효율적인 해킹

문제요약

컴퓨터 간 신뢰 관계를 참고하여 최대한 해킹할 수 있는 컴퓨터의 번호를 출력

 

난이도

Silver 1

---

풀이 포인트

• DFS
  • 항상 초기화 타이밍을 잘 맞춰줘야 함.
• 인접리스트
  • 컴퓨터 간 신뢰관계 인접리스트로 표현
• sort

//내림차순 정렬
sort(ret.begin(), ret.end(), greater<pair<int, int>>());

---

REVIEW

 

dfs문제는 이제 좀 익숙해진 것 같다.

 

모범 풀이 접근에서 배워야할 것은

 

#시간복잡도 어림짐작 하고 들어가는 습관

우선은 풀기 급급하기 때문에, 시간복잡도는 고려하지 않고 코드부터 짜기 시작하는데,

이 문제 같은 경우에도 최대 범위가 1만이므로 dfs로 모든 정점을 탐색한다 가정 하에, 최악의 시간복잡도가 O(n^2)이 되므로

계산횟수가 1억이 되어버리는 꽤나 시간복잡도가 높은 문제이기 때문에

다른 풀이가 없을지 한번쯤은 생각해보고 들어갔어야 했다.

 

#공간복잡도 : 최소한의 공간으로 효율적 활용

난 생각하기가 편하게끔 하나면 되는 저장 배열이나 벡터 공간을 너무 많이 마련하는 경향이 있는데,

이건 노하우가 좀 쌓여야할 듯.

 

# 최대 최소 갱신 그때그때 하는 것

나는 또 sort를 해주어 가장 마지막 값에 접근하는 식으로 했는데, 그때 그때 갱신하기.

 

# 초기화

정말 바보같은 실수이긴 한데,

디버깅을 한다고 hackdfs함수를 한번 돌리고, 정작 정답내기 위해 필요한 값에 할당할 함수를 한 번 더 돌려버렸다.

무슨 말이냐면, 방문배열을 초기화하지 않고서 디버깅 코드에 진짜 값을 넣어버리고 정작 필요한 코드엔 이상한 값을 넣어버리고 있었던 것..

항상 테스트 케이스가 여러개이기 때문에 초기화의 타이밍을 잘 체크할 것!

 

그래도 한번에 정답을 받아 짜릿했다..

인접의 u v를 뒤집어 생각하는 것도 약간의 트릭이었기에 남겨둠

 

---

CODE

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

int n, m, u, v;

vector<pair<int, int>> ret;
vector<int> computerN;

vector<int> adj[10004];
bool visited[10004];

int hack(int node)
{
    int cnt = 1;
    visited[node] = true;

    for (int i = 0; i < adj[node].size(); i++)
    {
        if (visited[adj[node][i]])
            continue;
        cnt += hack(adj[node][i]);
    }
    return cnt; 
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> v >> u;
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; i++)
    {
        // 초기화 잘 해주기
        memset(visited, false, sizeof(visited));

        if (!visited[i])
        {
            int k = hack(i);    //무슨 차이지, 한번 돌리면 memset안되니까 결과가 다르지.
            
            //cout << "현재 방문 노드는 " << i << '\n';
            //cout << "방문 노드로 부터 해킹한 컴퓨터는 " << k << "대\n";
            
            ret.push_back({k, i});
        }
    }

    for(int i = 0; i < ret.size(); i++){
        //cout << ret[i].first << "," << ret[i].second<<'\n';
    }

    // ret<해킹가능한 컴퓨터 대수, 컴퓨터 번호>
    sort(ret.begin(), ret.end(), greater<pair<int, int>>());

    for (int i = 0; i < ret.size(); i++)
    {
        //cout <<"정렬 후 \n";
        //cout << ret[i].first << "," << ret[i].second << '\n';
    }

    int max_hack_cnt = ret[0].first;//여기가 4가 되어야 해..
    //cout << "해킹할 수 있는 최대 컴퓨터는 " << max_hack_cnt <<'\n';

    for (int i = 0; i <ret.size() ; i++)
    {
        if (ret[i].first == max_hack_cnt)
        {
            //cout << ret[i].first <<"대 해킹할 수 있는 컴퓨터의 번호는 " << ret[i].second <<'\n';
            computerN.push_back(ret[i].second);
        }
    }

    sort(computerN.begin(), computerN.end());

    for (int a : computerN)
        cout << a << " ";

    return 0;
}

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

vector<int> v[10001];
int dp[10001], mx, visited[10001], n, m, a, b;

int dfs(int here)
{
    visited[here] = 1;
    int ret = 1;
    for (int there : v[here])
    {
        if (visited[there])
            continue;
        ret += dfs(there);
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    while (m--)
    {
        cin >> a >> b;
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        memset(visited, 0, sizeof(visited));
        dp[i] = dfs(i);
        mx = max(dp[i], mx);
    }
    for (int i = 1; i <= n; i++)
        if (mx == dp[i])
            cout << i << " ";
    return 0;
}