글 읽기 - 무엇이 잘못되었는지 모르겠네요 ㅜㅜ 반례가 있을까요?

ricky23 3년 전 0

논리구조는 이렇게 했습니다.

루트 노드는 1로 고정 했고,

DFS를 통해서 먼저 쭉쭉 들어갑니다

1) 만약 Leaf 노드이면 부모 노드를 Early Adopter로 만든다

2) 만약 자식 노드에 Early Adopter가 있으면 본인은 Early Adopter가 될 필요 없지만,

자식 중에 Early Adopter가 없으면 본인이 Early Adopter가 된다.

3) Root ( 1번 노드 ) 를 기준으로,

Root 노드가 만약 Early Adopter 이면 상관 없지만,

Early Adopter가 아닌데 자식노드들 중 Early Adopter가 아닌게 있다면 자신이 Early Adopter 가 된다.

ㅜㅜ 확인부탁드립니다

#include <iostream>
#include <vector>

using namespace std;

int result = 0;

void makeEarlyAdopter(vector<vector<int>> &childNodes, vector<bool> &visited, vector<bool> &earlyAdopter, int curRoot, int parent) {
    if(childNodes[curRoot].size() == 1 && curRoot != 1) {
        if(!earlyAdopter[parent]) {
            earlyAdopter[parent] = true;
            cout << parent << '\n';
            result++;
        }
        return;
    }

    bool childAdopterFlag = false;
    for( const int child : childNodes[curRoot] ) {
        if(!visited[child]) {
            visited[child] = true;
            makeEarlyAdopter(childNodes, visited, earlyAdopter, child, curRoot);
        }
        if(earlyAdopter[child]) childAdopterFlag = true;
    }

    if(earlyAdopter[curRoot]) return;
    else if( curRoot == 1 ) {
        for( const auto child : childNodes[1] ) {
            if(!earlyAdopter[child]) {
                result++;
                cout << 1 << '\n';
                break;
            }
        }
        return;
    }
    else if( childAdopterFlag ) return;
    else {
        earlyAdopter[curRoot] = true;
        cout << curRoot << '\n';
        result++;
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    int nodeNumber, u, v;
    cin >> nodeNumber;

    vector<vector<int>> childNodes(nodeNumber + 1);
    vector<bool> visited(nodeNumber + 1);
    vector<bool> earlyAdopter(nodeNumber + 1);

    for( int i = 1; i < nodeNumber; i++ ) {
        cin >> u >> v;
        childNodes[u].emplace_back(v);
        childNodes[v].emplace_back(u);
    }


    cout << "Early Adopter" << '\n';

    visited[1] = true;
    makeEarlyAdopter(childNodes, visited, earlyAdopter, 1, 1);

    cout << "result" << '\n';

    cout << result;

    return 0;

}

byunjaewoo 3년 전 0

풀이를 잘못 떠올리신 것 같습니다.

지금 반례는 못 찾겠지만, 분명 존재합니다.

정해는 트리 DP입니다.

DP1[i] = i의 서브트리에서 i를 얼리어답터로 했을 때 필요한 최소 개수

DP2[i] = i의 서브트리에서 i를 얼리어답터로 하지 않았을 때 필요한 최소 개수

이렇게 식을 정의하면 풀립니다.

+ 65번 줄, 70번 줄은 디버깅하면서 쓴 것 같은데 지워주셔야 합니다.

shw2495 3년 전 2

저는 비슷한 방법을 써서 풀었습니다. 아마 틀리신 이유가

2) 만약 자식 노드에 Early Adopter가 있으면 본인은 Early Adopter가 될 필요 없지만,

자식 중에 Early Adopter가 없으면 본인이 Early Adopter가 된다.

가 아닌

2) 만약 자식 노드가 하나라도 Early Adopter가 아니면 본인이 Early Adopter가 된다.

-> 모든 친구들이 early adopter이어야 받아드리기 때문입니다.

이 부분만 수정하면 통과하실 것 같습니다.

//반례
11
2
3
4
5
6
7
8
9
10
11
//답: 5
//출력: 4

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

문제

문제

출처

ICPC

무엇이 잘못되었는지 모르겠네요 ㅜㅜ 반례가 있을까요?

ricky23 3년 전 0

byunjaewoo 3년 전 0

shw2495 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말