[백준] 1967번 트리의 지름 (= tree diameter) - 재우스 프로그래밍 (C 언어)

문제 링크 : www.acmicpc.net/problem/1967

#include <stdio.h>
#include <stdlib.h>    //malloc, free
#include <stdbool.h>

#define DEBUG 0
#define MAX_NODE_NUM 10000

typedef struct _SNode {
    int mParentNum;
    int mChildNum;
    int mLength;
} SNode;

typedef struct _SVisit {
    bool mVisit;
    int mLength;
} SVisit;

SNode arrInputTree[MAX_NODE_NUM - 1];    //간선 개수 = 노드 개수 - 1
SVisit arrStruVisit[MAX_NODE_NUM];

int nodeNum;
void initSNode(SNode *);    //parent node, child node, length 포함한 SNode 초기화
void initInputTree(void);    //input tree 초기화
void initSVisit(SVisit *);    //visit여부 입력값과의 length 포함한 SVisit 초기화
void initArrStruVisit(void);    //SVisit 구조체 배열 초기화
void doDFS(int, int);    //입력 노드로부터의 거리를 구하는 함수
void checkVisit(int, int);    //방문했는지 여부와 거리를 저장해주는 함수
int findFarthestNode();

int main(void)
{
    scanf("%d", &nodeNum);

    initInputTree();

    //arrInputTree 입력 받음
    for (int i = 0; i < nodeNum - 1; i ++) {
        scanf("%d", &arrInputTree[i].mParentNum);
        scanf("%d", &arrInputTree[i].mChildNum);
        scanf("%d", &arrInputTree[i].mLength);
    }

    doDFS(1, 0);    //최초 시작 노드 1, 최초 노드로부터의 거리 0 입력

    int farthestNum = findFarthestNode();
    initArrStruVisit();
    doDFS(farthestNum, 0);

    farthestNum = findFarthestNode();

    printf("%d\n", arrStruVisit[farthestNum - 1].mLength);

    return 0;
}

void doDFS(int inputNum, int length)
{
    checkVisit(inputNum, length);    //visit 구조체 배열에 방문 여부와 최초 재귀 함수 입력값으로부터의 거리 입력

    //visit해서 최초 함수 입력값으로부터의 거리를 입력 받은 노드는 방문을 안하고
    //방문 안한 노드는 방문해서 거리 입력하기
    for (int i = 0; i < nodeNum - 1; i++) {
        //재귀 함수 입력값과 inputTree의 paretNum값이 일치하고
        //visit하지 않았을 경우에 방문 체크 및 거리 저장하면서 재귀 호출
        if (inputNum == arrInputTree[i].mParentNum && !arrStruVisit[arrInputTree[i].mChildNum - 1].mVisit) {
            doDFS(arrInputTree[i].mChildNum, length + arrInputTree[i].mLength);
        }
        //재귀 함수 입력값과 inputTree의 childNum값이 일치하고
        //visit하지 않았을 경우에 방문 체크 및 거리 저장하면서 재귀 호출
        else if (inputNum == arrInputTree[i].mChildNum && !arrStruVisit[arrInputTree[i].mParentNum - 1].mVisit) {
            doDFS(arrInputTree[i].mParentNum, length + arrInputTree[i].mLength);
        }
    }
    return;
}

void checkVisit(int inputNum, int sumLength)
{
    arrStruVisit[inputNum - 1].mVisit = true;
    arrStruVisit[inputNum - 1].mLength = sumLength; 

    return;
}

void initSNode(SNode *struNode)
{
    struNode->mParentNum = 0;
    struNode->mChildNum = 0;
    struNode->mLength = 0;

    return;
}

void initInputTree(void)
{
    for (int i = 0; i < MAX_NODE_NUM - 1; i++) {
        initSNode(&arrInputTree[i]);
    }

    return;
}

void initSVisit(SVisit *struVisit)
{
    struVisit->mVisit = false;
    struVisit->mLength = 0;

    return;
}

void initArrStruVisit(void)
{
    for (int i = 0; i < MAX_NODE_NUM; i++) {
        initSVisit(&arrStruVisit[i]);
    }

    return;
}

int findFarthestNode()
{
    int farthestNum = 0;
    int farthestNode = 0;

    for (int i = 0; i < nodeNum; i++) {
        if (farthestNum < arrStruVisit[i].mLength) {
            farthestNum = arrStruVisit[i].mLength;
            farthestNode = i;
        }
    }

    return farthestNode + 1;    //arrStruVisit배열은 0부터 시작하는데 노드는 1부터 시작하므로 + 1
}