글 읽기 - 제 방법이 틀린걸까요?

ujunhwan 3년 전 0

1번 노드는 항상 존재하므로 1번 노드를 기준으로 하여 왼쪽의 최대 길이와 오른쪽 최대 길이를 bfs 2번을 이용하여 구한 뒤, 더하는 방식으로 코드를 구성하였습니다.

이 게시판에 있는 반례나 제가 만들어본 테스트케이스, 예제의 경우 다 통과가 되는 상황에서 무엇이 틀린지 모르겠어서 질문글을 올려봅니다

혹시 방법 자체가 틀린걸까요?

// 1167번 트리의 지름
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
static const int MAX = 100000;
int n, dist[MAX + 1], vst[MAX + 1];
vector<pair<int, int> > adj[MAX + 1];
queue<int> q;
long long bfs(int x) {
    long long ans = dist[x];
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < adj[x].size(); i++) {
            int nxt = adj[x][i].first;
            int cst = adj[x][i].second;
            if (dist[nxt] == 0) {
                q.push(nxt);
                dist[nxt] = dist[x] + cst;
                if (dist[nxt] > ans) ans = dist[nxt];
            }
        }
    }
    return ans;
}
long long go(int x) {
    long long ret = 0;
    dist[x] = 1;
    for (int i = 0; i < adj[x].size(); i++) {
        int y = adj[x][i].first;
        dist[y] = adj[x][i].second;
        q.push(y);
        ret += bfs(y);
    }
    return ret;
}
int main () {
    scanf("%d", &n);
    while (n--) {
        int x, y, z;
        scanf("%d", &x);
        while (z != -1) {
            scanf("%d", &y);
            if (y == -1) break;
            scanf("%d", &z);
            adj[x].push_back(make_pair(y, z));
        }
    }
    printf("%lld\n", go(1));
    return 0;
}

sait2000 3년 전 1

말씀하신 내용이랑 코드가 조금 다른 것 같네요. 1번 노드에 대해 자식을 다 돌면서 bfs의 결과값을 더하고 있는데 자식이 1개이거나 2개보다 많을 때는 답이 이상할 거 같네요

그리고 방법도 틀렸습니다. 예를 들어 아래같은 트리가 있다고 하면 답이 틀리겠죠. 이 경우 트리의 지름은 2의 왼쪽 맨 아래부터 2의 오른쪽 맨 아래가 될 테지만 설명해주신 방벚대로 하면 2의 한쪽 끝부터 3까지의 거리가 답으로 나오겠네요.

      1
     / \
    2   3
   / \
  o   o
  |   |
  o   o
  |   |
  ...

ujunhwan 3년 전 0

@sait2000 감사합니다 제가 완전 이해를 잘못했었네요'!!

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

문제

문제

출처

ICPC

제 방법이 틀린걸까요?

ujunhwan 3년 전 0

sait2000 3년 전 1

ujunhwan 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말