글 읽기 - [C++] DFS로 해결한 것 같은데 '틀렸습니다'가 나와서 질문드립니다.

npcplayer0206 1년 전 0

어떤 부분이 틀렸는지 감이 오질 않습니다. 한 번 확인해주실 수 있을까요?

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// "child가 parent를 신뢰한다.", result : DFS의 결과, curr : 현재까지 result중 최댓값,
// childs : 자식의 개수를 DP로 저장, Numlist : 출력할 숫자의 모음,
// V[parent] : 해당 parent를 믿는 child를 저장
int N, M, child, parent, result, curr, childs[10001];
queue<int> Numlist;
vector<int> V[10001];

// DFS : childs라는 dp에 저장되어있으면 바로 값을 반환,
//       값이 없으면 입력된 parent(int e)를 신뢰하는 child의 개수와
//       각각의 child를 신뢰하는 child들의 수를 cnt에 저장하여 childs[e]를 갱신하고 반환
int DFS(int e){
    if(childs[e] != 0) return childs[e];
    int cnt = 0;
    for(int v = 0; v < V[e].size(); v++){
        cnt += 1 + DFS(V[e][v]);
    }
    return childs[e] = cnt;
}

int main()
{
    cin >> N >> M;
    for(int m=0; m<M; m++){
        cin >> child >> parent;
        V[parent].push_back(child);
    }
    for(int v=1; v<=N; v++){
        result = DFS(v);
        if(result == curr){        // 결과가 현재 최댓값과 같다면 Numlist뒤에 추가
            Numlist.push(v);
        }
        else if(result > curr){    // 결과가 현재 최댓값보다 크다면 Numlist를 비우고, 추가
            while(!Numlist.empty()) Numlist.pop();
            curr = result;
            Numlist.push(v);
        }
    }

    // 출력하는 구간.
    cout << Numlist.front();
    Numlist.pop();
    while(!Numlist.empty()){
        cout << " " << Numlist.front();
        Numlist.pop();
    }
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] DFS로 해결한 것 같은데 '틀렸습니다'가 나와서 질문드립니다.

npcplayer0206 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말