백준 1325번 효율적인 해킹

문제 링크 : https://www.acmicpc.net/problem/1325

입력값 수의 범위가 너무 크길래 2차원 인접행렬로 구혔했다가는 메모리가 너무 많이필요할것같아서

2차원 벡터를 사용하여 인접해있는 정보를 추가해주어야 겠다고 생각했다.

그러나 c++로 알고리즘을 푼지 얼마 안된나는 2차원 벡터는 커녕 1차원 벡터도 낯설었기 때문에 2차원 벡터를 구글링하였다.

하지만 검색결과가 탐탁지 않아서 1325번 효율적인 해킹문제를 푼사람의 코드를 보고 2차원 벡터 구현을 참고하려고 검색을 하였는데

2차원벡터 선언과 사용을 보다가 그만 소스를 너무 많이 봐버렸다.

물론 대략적인 구상은 한 채로 소스를  보긴 했지만 구체척으로 구상하지 않은 상태에서 완성된 소스를 봐버려서

vitit배열 사용과 해킹할수있는 컴퓨터수의 최대값을 저장하여 마지막에 그값과 같은 값을 가지는 컴퓨터의 번호를 출력하는것 등 의도치않게 그 블로그에 있던 코드를 좀 많이 참고하게 되었다..

일단 푼 방법은

1. 입력값을 2차원 배열에 저장한다.

2. 배열을 순회하며 각 컴퓨터를 기준으로 dfs를 실행하며 해킹할수있는 컴퓨터의 수를 구하고 그 값을 hacking배열에 저장하고 그 중 최대값을 max_count에 유지한다.

3. hacking배열을 순회하며 max_count와 같은 값을 가지는 컴퓨터의 번호를 출력한다.

이렇게 풀었다.

c++로 풀었음에도 불구하고 시간이 3644ms나 걸렸다. 효율적으로 풀지 못한것같다.

물론 문제의 제한시간은 5초긴 했지만 그래도 맞은사람들 보면 세자리ms인 사람도있고 천이나 이천대도 많은걸보면 삼천대는 좀 아쉬운것같다.

아무튼 아래는 소스코드이다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
 
vector<int> graph[10001];
bool visit[10001] = { false };
int hacking[10001] = { 0 };
int max_count = 0 ;
 
void dfs(int current, int start) {
    visit[current] = true;
 
    for (int i = 0; i < graph[current].size(); i++) {
        int next = graph[current][i];
        if (visit[next] == true) continue;
 
        dfs(next, start);
        hacking[start] += 1;
    }
}
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t2 >> t1;
        graph[t1].push_back(t2);
    }
 
    for (int i = 0; i <= n; i++) {
        if (graph[i].size() == 0) continue;
 
        memset(visit, false, sizeof(bool)*(n+1));
        dfs(i, i);
        max_count = max(max_count, hacking[i]);
    }
 
    for (int i = 0; i <= n; i++) {
        if (hacking[i] == max_count) {
            cout << i << " ";
        }
    }
}