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

0. [c++] 백준

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

1. 풀이

DFS를 활용해서 문제를 풀어보았다.

자손노드를 방문해서 개수가 증가 할 때 마다 부모 노드의 count를 1씩 증가시켜 주었다.

사실 처음에는 메모이제이션을 활용하여서 문제를 해결하려고 했었는데, 그때의 문제는 순환하는 형태의 답을 가지고 있는 경우였다. 

 나는 이미 방문한 경우라면 count[here] + 1 을 반환하는 구조로 만들었었는데, 순환하는 부분을 마주하게 되면 이미 방문한 곳의 visited는 true가 되어있어 이상한 답을 반환해버렸다.

그래서 처음 말했던 것과 같이 구현을 하게 되었다.

+) 근데, 다 만들고 나서 생각을 해보니 메모이제이션을 활용할 방법이 있는 것 같기는 하다.

visited를 int로 선언하고, 0은 방문하지 않은 경우, 1은 방문하였는데 아직 종료가 되지 않은 경우(이 경우에서 다시 자신을 만나게 된다면, 이 루프는 순환 루프로 결정되고, 이들과 관련된 노드들은 전부 찾아 모두 같은 수로 만들어준다.)

2는 방문이 끝난 경우로 만든다면 아마 가능하지 않을까 싶다.

2. 소스코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
//vector<pair<int, int> > trust;
//trust[i]는 자신을 신뢰하는 컴퓨터를 자손 노드로 갖는다.
vector<int> trust[10001];
bool visited[10001];
pair<int,int> Count[10001];
 
bool comp(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first)
        return a.second < b.second;
    else
        return a.first > b.first;
}
 
 
//첫번째 구현은 틀렸다. 왜냐하면 자손노드를 2번 방문하는 경우는 고려하지 못했기 때문이다.
void calcHackComputer(int here, int mather) {
    //기저 사례 : 이미 방문한 노드이면 종료
    if (visited[here])
        return;
    visited[here] = true;
 
    for (int i = 0; i < trust[here].size(); i++) {
        if (!visited[trust[here][i]]) {
            Count[mather].first++;
            calcHackComputer(trust[here][i], mather);
        }
    }
    Count[mather].first++;
}
 
int main() {
    int N, M,a,b;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        //trust.push_back({ a,b });
        //a가 b를 신뢰하므로 이를 vector에 반영한다.
        trust[b].push_back(a);
    }
 
    for (int i = 1; i <= N; i++) {
        memset(visited, false, sizeof(visited));
        calcHackComputer(i, i-1);
        Count[i-1].second = i;
    }
    
 
    sort(Count, Count + N, comp);
 
    int temp = Count[0].first;
 
    for (int i = 0; i < N; i++) {
        //cout << Count[i].second << " : " << Count[i].first << endl;
 
        if (Count[i].first == temp) {
            cout << Count[i].second << " ";
        }
        else {
            break;
        }
    }
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!