BOJ 백준 1167 : 트리의 지름

시작하면서

　이번 문제는 트리(Tree) 문제이다.

BOJ 1167 - 트리의 지름

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 4가지이다.

• V : 트리 정점의 개수
• nodeIndex : 노드의 인덱스
• pairValue0 : 해당 노드와 연결된 정점 번호
• pairValue1 : 해당 노드와 연결된 정점까지의 거리

​

문제 아이디어

　처음에 생각한 아이디어는 다음과 같았다.

1. 간선을 1가지만 가지고 있는 노드, 즉 리프(leaf) 노드들 중 하나를 선정한다. (아무거나)
2. 해당 노드에서 BFS를 사용해서 도달할 수 있는 최대의 거리를 구한다.

하지만 해당 알고리즘은 풀리지 않았다. 곰곰히 생각해보니 예외 사항들이 있다는 것을 알았다. 그래서 혼자 열심히 생각해봤지만 좋은 생각이 떠오르지 않았다.

생각보다 쉬워보였는데 풀리지 않았고, 질문 검색 페이지를 읽다가 처음에 생각한 아이디어를 2번 반복하면 된다는 답변이 있었다.

즉, 아무 리프 노드에서 가장 멀리 있는 정점을 찾고, 해당 정점에서 가장 멀리 있는 정점까지의 길이를 찾으면 트리의 지름이다.

​

해결

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

void InputNode(vector<vector<pair<int, int> > > &nodes, int V, int* pOutLeafIndex);
void BFS(const vector<vector<pair<int, int> > > &nodes, pair<int, int> &resultPair, bool* bVisited, int startIndex, int V);

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    vector<vector<pair<int, int> > > nodes;
    pair<int, int> resultPair = make_pair(0, 0);
    int V = 0, leafIndex = -1;
    bool* bVisited;

    // Input V
    cin >> V;
    nodes.resize(V + 1);
    bVisited = new bool[V + 1];

    // Input Nodes
    InputNode(nodes, V, &leafIndex);

    // BFS x2
    BFS(nodes, resultPair, bVisited, leafIndex, V);
    BFS(nodes, resultPair, bVisited, resultPair.first, V);

    // Result
    cout << resultPair.second;

    delete[] bVisited;

    return 0;
}

void InputNode(vector<vector<pair<int, int> > >& nodes, int V, int *pOutLeafIndex)
{
    int nodeIndex = 0, pairValue0 = 0, pairValue1 = 0;

    for (int i = 0; i < V; i++)
    {
        cin >> nodeIndex;

        int nodeCount = 0;

        while (true)
        {
            cin >> pairValue0;

            if (pairValue0 == -1)
                break;

            cin >> pairValue1;

            nodes[nodeIndex].push_back(make_pair(pairValue0, pairValue1));
            nodeCount++;
        }

        if (*pOutLeafIndex == -1 && nodeCount == 1)
        {
            *pOutLeafIndex = nodeIndex;
        }
    }
}

void BFS(const vector<vector<pair<int, int> > > &nodes, pair<int, int> &resultPair, bool *bVisited, int startIndex, int V)
{
    queue<pair<int, int> > bfsQueue;

    bfsQueue.push(make_pair(startIndex, 0));
    resultPair = make_pair(0, 0);

    memset(bVisited, false, sizeof(bool) * (V + 1));

    while (bfsQueue.empty() == false)
    {
        int bfsIndex = bfsQueue.front().first;
        int bfsValue = bfsQueue.front().second;
        bfsQueue.pop();

        bVisited[bfsIndex] = true;
        if (bfsValue > resultPair.second)
        {
            resultPair = make_pair(bfsIndex, bfsValue);
        }

        int bfsSize = nodes[bfsIndex].size();
        for (int i = 0; i < bfsSize; i++)
        {
            if (bVisited[nodes[bfsIndex][i].first] == true)
                continue;

            bfsQueue.push(make_pair(nodes[bfsIndex][i].first, bfsValue + nodes[bfsIndex][i].second));
        }
    }
}

​

마치며

　구글링을 통해 검색해보니 트리의 지름은 이미 증명이 되어있는 알고리즘이었다. 아마 스터디원들 중에 한 명이라도 알고 있었다면 해당 문제를 선택하지 않았을 것 같다. 하지만 알고리즘 인덱스가 하나 늘어나서 기분이 좋아지는 문제였다!