글 읽기 - 아무리 고민해도 풀리지 않는 문제.. 반례 부탁드립니다.

lgun202 2년 전 0

안녕하세요. 여러 해설을 찾다보니 쉽게 푸는 정답을 알긴했는데

이 방식으로는 계속 왜 6%에서 틀렸다고 나오는지 궁금해서 질문 글을 올립니다.

답변해주시면 정말로 진심으로 감사드리겠습니다.

먼저 트리를 입력 받을 때 정점이 작은 순(위에서부터)부터 입력 되기 때문에 입력을 하면서

ist[i][v] = dist[i][u] + dist[u][v]; 이런식으로 정점 1에서 모든 정점으로의 길이, 정점 2에서 모든 정점으로의 길이 등을 다 저장해주었습니다.

그런다음 childNode의 개수도 같이 카운트해주어서 leafNode를 따로 List에 저장해주었습니다.

그리고 입력을 받으면서 각 정점에다가 각 정점의 부모노드로 뭐가 있는지도 저장해주었습니다.

ex) 문제 테스트케이스

1의 부모노드로는 있습니다.
2의 부모노드로는 1 있습니다.
3의 부모노드로는 1 있습니다.
4의 부모노드로는 1 2 있습니다.
5의 부모노드로는 1 3 있습니다.
6의 부모노드로는 1 3 있습니다.
7의 부모노드로는 1 2 4 있습니다.
8의 부모노드로는 1 2 4 있습니다.
9의 부모노드로는 1 3 5 있습니다.
10의 부모노드로는 1 3 5 있습니다.
11의 부모노드로는 1 3 6 있습니다.
12의 부모노드로는 1 3 6 있습니다.

이런식으로 입니다.

그런다음 각 mid별로 dist[mid][leafNode] 반복시키면

mid: 1
edge value: 28, parents 3
edge value: 21, parents 3
edge value: 17, parents 3
edge value: 17, parents 3
edge value: 15, parents 2
edge value: 9, parents 2

mid: 2
edge value: 12, parents 4
edge value: 6, parents 4

mid: 3
edge value: 26, parents 5
edge value: 19, parents 6
edge value: 15, parents 5
edge value: 15, parents 6

mid: 4
edge value: 7, parents 0
edge value: 1, parents 0

mid: 5
edge value: 15, parents 0
edge value: 4, parents 0

mid: 6
edge value: 10, parents 0
edge value: 6, parents 0

이런식으로 각 mid에서 내림차순으로 (mid->리프노드) 의 (가중치 값, mid 바로 아래에 있는 child->parents라 표현) 값으로 정렬을 할 수 있습니다. 그런다음 parents 같으면 서로 간선이 겹치는 최댓값이 나오므로 간선이 겹치지 않는, mid바로 아래 child가 겹치지 않는 다른 상위 2개의 edge value를 더해줘서 구하면 길이 최댓값이 나온다고 생각했습니다.

그 외 편향트리인 경우, 위 리프노드의 부모가 mid가 되는 경우 parents가 0으로 뜨는 경우 모두 처리해주었습니다.

그래서 백준 질문 글에 나와있는 테스트 케이스들은 전부 맞았는데 바로 6%에서 틀려버리니 뭐가 완전히 잘못된 것 같습니다. 해당 부분 반례 찾아주시면 진심으로 감사드리겠습니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

typedef struct NODE{
    int v, e; // v 도착지, e 간선 가중치 값
    NODE(int vi, int ei):v(vi),e(ei){};
}NODE;

typedef struct RANK{
    int edge; // 간선 가중치 값
    int parent; // 부모 노드
    RANK(int e, int p):edge(e),parent(p){};
}RANK;

bool compare(RANK a, RANK b){ // 간선 가중치 값으로 내림 차순 정렬
    return a.edge > b.edge;
}

char dist[10001][10001]={0}; // 인접행렬 구현
char isHasChild[10001]={0}; // child 개수 카운트.
set<int> leafNode; // 리프노드 리스트 
set<int> parents[10001]; // 각 정점을 idx로 해서 각 정점에 정점의 부모노드들 추가.
int n;

int maxLength = 0; // 최댓값

int main()
{
    //트리 입력
    scanf("%d",&n);
    for(int i=0; i<n-1; i++){
        int u, v, e;
        scanf("%d %d %d",&u, &v, &e);
        isHasChild[u]++; // 자식노드를 가지고 있다고 넣어줌.
        dist[u][v] = e;
        parents[v].insert(u);

        for(int i=1; i<=n; i++){
            if(dist[i][u] != 0){
                dist[i][v] = dist[i][u] + dist[u][v];
                parents[v].insert(i);
            }
        }
    }

    // 리프노드 목록 추가
    for(int i=1; i<=n; i++){
        if(isHasChild[i]==0){
            leafNode.insert(i);
        }
    }

    //선형 트리인 경우
    if(leafNode.size() == 1){
        for(int i=1; i<n; i++){
            maxLength+=dist[i][i+1];
        }
        printf("%d",maxLength);
        return 0;
    }

    //최종 최장길이max는 maxLength에 저장
    //최장길이 구하는 Process
    for(int mid=1; mid<=n; mid++){ //mid 1~leaf노드 전까지 반복
        if(leafNode.find(mid)!=leafNode.end()) continue; // 만약 리프노드가 mid로 설정되면 continue;
        vector<RANK> leafList; // mid를 부모로 갖는 리프리스트.
        //RANK는 
        //int edge(간선 가중치), 
        //int parent(leafNode가 mid 바로 아래 child 노드들 중 어떤 노드에 속하는지)
        //상위 2개의 edge 값이 서로 다른 (mid 바로 아래 )child로 되어있다면 그게 max이기 때문

        //리프노드들 중에서 mid를 부모로 갖는 리프노드들을 childList에 넣기
        set<int>::iterator iter;
        for(iter=leafNode.begin(); iter!=leafNode.end(); iter++){ // 각 리프노드들 루프 돌리기
            set<int>::iterator isHasMid;
            //printf("mid: %d iter: %d\n",mid, *iter);
            isHasMid = parents[*iter].find(mid);
            if(isHasMid!=parents[*iter].end()){ //부모중에 mid가 있다면
                parents[*iter].erase(isHasMid); // 부모 리스트에서 mid 제거
                leafList.push_back(RANK(dist[mid][*iter], *parents[*iter].begin())); 
                // 이번 mid를 부모로 하는 child로 RANK(간선 값, mid바로 아래 노드 값)으로 추가.
            }
        }
        sort(leafList.begin(), leafList.end(), compare); // leafList를 간선값이 큰것으로 정렬

        int midMaxVal = 0;
        midMaxVal += leafList[0].edge; // 일단 간선 값 가장 큰 리프노드(mid->leaf)는 그냥 더함.
        //마지막 리프노드 위에서의 간선 계산할 경우.
        if(leafList[0].parent == 0 && leafList[1].parent == 0){
            midMaxVal += leafList[1].edge;
        }
        else{ //parent가 다른 mid->leaf 노드 간선 값을 더해줌.
            for(int i=1; i<leafList.size(); i++){
                if(leafList[0].parent != leafList[i].parent){
                    midMaxVal += leafList[i].edge;
                    break;
                }
            }
        }
        
        // child가 2 미만이면 분기점이 아님. mid가 될 수 없음.
        if(isHasChild[mid]<2) {
            if(mid!=1) continue;
            if(mid==1){ //mid가 아니지만 루트노드부터 시작해서 최대값이 만들어지는 경우가 있음.
                //편향트리에서 빠져나온 경우 
                if(maxLength<leafList[0].edge){
                    maxLength=leafList[0].edge;
                }
            }
        }

        //최댓값 교체
        if(maxLength < midMaxVal) maxLength = midMaxVal;
    }
    printf("%d",maxLength);
    return 0;
}

kopasd99 2년 전 0

크흠....

55murphy 2년 전 2

dist, isHasChild 자료형이 char이라서 정점 A에서 여러 정점들을 거쳐 점점 B까지의 거리가 char에 담을수 있는 값을 벗어나면 오답을 출력하는것 같아요

입력:
5
1 2 100
1 3 100
2 4 100
3 5 1
정답: 301
오답: 45
---
입력:
4
1 2 100
1 3 100
2 4 57
정답: 257
오답: 1
---
입력:
5
1 2 100
1 3 100
2 4 100
3 5 100
정답: 400
오답: 0

lgun202 2년 전 0

감사합니다. 덕분에 해당 문제점을 알고 기존의 인접행렬 dist를 map<short, int>를 이용한 인접리스트로 변경해서 데이터 크기를 최대한 절감하였지만 40% 부분에서 메모리초과가 뜨네요 :(

그래도 덕분에 뭐가 문제인지 알게되어서 속이 시원합니다 ㅎㅎ,,, 감사합니다!!

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

문제

문제

출처

ICPC

아무리 고민해도 풀리지 않는 문제.. 반례 부탁드립니다.

lgun202 2년 전 0

kopasd99 2년 전 0

55murphy 2년 전 2

lgun202 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말