글 읽기 - BFS 활용한 풀이, 4%에서 계속 틀림

khy2714 7달 전 0

BFS를 두 번 활용해서 문제를 해결했습니다.

일단 트리의 루트 노드는 트리의 아무 노드를 임의로 선택(1번 노드)해서 루트 노드라고 가정하고 풀었습니다.

먼저 모든 잎 노드를 큐에 넣은 후에 BFS를 돌려서 각 잎 노드에서 루트 노드를 향하는 방향으로 거리를 진행해주었습니다.

질문 게시판에 올라온 반례를 모두 다 적용했는데 맞는 풀이로 떠서

어느 부분이 잘못된 건지 모르겠네요ㅠ

반례나 제 코드에서 틀린 부분 알려주신다면 정말 감사드리겠습니다..!!

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 100001

int V;
typedef struct _node
{
    int data, dist;
    struct _node *last;
    struct _node *next;
} Node;

Node *createNode(int adj, int dis)
{
    Node *new = (Node *)malloc(sizeof(Node));
    new->data = adj;
    new->dist = dis;
    new->last = new;
    new->next = NULL;
    return (new);
}

void getLevel(Node *tree[], int *level)
{
    // 큐 선언
    int queue[SIZE], front = -1, rear = -1;
    // 노드 번호
    int cur, nxt;
    // 노드
    Node *node;
    // 1번 노드를 루트 노드라고 생각하고 enqueue
    queue[++rear] = 1;
    level[1] = 1;
    // 큐 빌 때까지 반복문
    while (front != rear)
    {
        cur = queue[++front];
 //       printf("%d level: %d\n", cur, level[cur]);
        node = tree[cur];
        while (node != NULL)
        {
            nxt = node->data;
            if (level[nxt] == 0)
            {
                level[nxt] = level[cur] + 1;
                queue[++rear] = nxt;
            }
            node = node->next;
        }
        
    }
}

int BFS(Node *tree[], bool *end, int *level)
{
    int max = 0, dist[SIZE] = {0,};
    // 큐 선언
    int queue[SIZE], front = -1, rear = -1;
    int cur, nxt;
    Node *node;
    // 큐에 시작하는 위치 넣기
    for (int i = 1 ; i <= V ; i++)
    {
        if (end[i] == 1)
        {
            queue[++rear] = i;
            dist[i] = 1;
        }
    }
    // 큐가 빌 때까지 반복
    while (front != rear)
    {
        cur = queue[(++front)%SIZE];
        if (dist[cur] - 1 > max) max = dist[cur] - 1;
        node = tree[cur];
//        printf("%d dist: %d\n", cur, dist[cur]);
        while (node != NULL)
        {
            nxt = node->data;
            if (level[cur] > level[nxt])
            {
                if (dist[nxt] + dist[cur] + node->dist - 2 > max)
                    max = dist[nxt] + dist[cur] + node->dist -2 ;
                if (dist[nxt] < dist[cur] + node->dist) 
                { 
                    dist[nxt] = dist[cur] + node->dist;
                    queue[(++rear)%SIZE] = nxt;
                }
            }
            node = node->next;
        }
    }
    return (max);
}

int main(void)
{
    // 트리의 정점의 개수 입력 받기
    scanf("%d", &V);
    // 입접 리스트를 활용해서 트리 입력 받기
    int i;
    int idx, adj, dis;
    bool end[SIZE]; // 연결된 노드의 개수가 하나인지 그 이상인지 세기 -> 트리의 끝 부분인지 확인하는 용도임
    Node *node, *next;
    Node *tree[SIZE] = {0, };
    for (i = 1 ; i <= V ; i++)
    {
        scanf("%d %d %d", &idx, &adj, &dis);
        node = createNode(adj, dis);
        tree[idx] = node;
        end[idx] = true;
        scanf("%d", &adj);
        while (adj != -1)
        {
            scanf("%d", &dis);
            next = createNode(adj, dis);
            node->last->next = next;
            node->last = next;
            end[idx] = false;
            scanf("%d", &adj);
        }
    }
    // 레벨 구하기
    int level[SIZE] = {0, };
    getLevel(tree, level);
    // BFS-> 최댓값 찾기
    int max = BFS(tree, end, level);
    printf("%d", max);
}

kokosoko59 7달 전 0

잎에서 루트까지의 거리중에서 최대가 트리의 지름이 아닌경우도 있습니다.

다른말로 하면, 트리의 지름은 잎에서 잎까지의 거리일수도 있습니다.

khy2714 7달 전 0

그래서

if (dist[nxt] + dist[cur] + node->dist - 2 > max)
max = dist[nxt] + dist[cur] + node->dist -2 ;

이 조건문을 달아줬습니다!

khy2714 7달 전 0

앗 틀린 이유 찾았습니다! 감사합니다!

사용한 반례:

12
1 2 1 3 1 -1
2 1 1 4 3 5 5 -1
3 1 1 6 1 -1
4 7 2 2 3 -1
5 2 5 8 4 9 2 -1
6 3 1 10 1 11 1 -1
7 4 2 -1
8 5 4 12 5 -1
9 5 2 -1
10 6 1 -1
11 6 1 -1
12 8 5 -1

결과:

답:

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

문제

문제

출처

ICPC

BFS 활용한 풀이, 4%에서 계속 틀림

khy2714 7달 전 0

kokosoko59 7달 전 0

khy2714 7달 전 0

khy2714 7달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말