[백준] 1167번 트리의 지름

문제

https://www.acmicpc.net/problem/1167

풀이과정

이제는 DFS, BFS 구현에 대해 좀 감이 오나 싶었는데 아직도 구현이 서툰 것 같다. 기본적인 구현문제들을 다시 한 번 풀어봐야겠다. 이 문제는 트리의 지름을 구하는 문제로 트리의 지름을 구하는 방법은 정해져있다. 먼저 임의의 정점부터 모든 정점까지의 거리를 구하여 가장 먼 거리를 가진 정점을 구한다. 그 후에 그 정점으로부터 모든 정점까지의 거리를 다시 구해서 그 거리들 중 가장 먼 값이 트리의 지름이 된다.

시간제한 1시간을 잡고 풀었는데 DFS로 풀어야할 것 같다고 생각하여서 한시간동안 개뻘짓을 했다. 또 가중치를 pair로 저장할 생각을 하지않고 또 다른 배열을 만들어서 저장하려해서 구현이 복잡해져서 각 정점까지의 거리를 어떻게 구할까 생각하다가 시간이 다 지났다. 그리고 검색을 통해 해결했는데 BFS를 통해서 1에서 시작하여 1부터 모든 정점까지의 거리를 dist[정점]에 저장해주고 그 거리들 중 가장 큰 값을 가진 정점부터 다시 탐색을 시작하여 가장 먼 거리를 지름으로 출력했다.

나중에 다시 한 번 풀어봐야겠다.

소스코드

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

#define MAX 100001

int N;
int ans;
int dist[MAX];
bool chk[MAX];
vector<pair<int,int>> a[MAX]; // first : 정점, second : 비용

void BFS(int start)
{
    fill(chk, chk + MAX, false);
    fill(dist, dist + MAX, 0);
    //memset(chk, false, sizeof(chk)); // 초기화
    //memset(dist, 0, sizeof(dist)); // 초기화

    queue<int> q;

    chk[start] = true;
    q.push(start);

    while (!q.empty())
    {
        int node = q.front();
        q.pop();

        for (int i = 0; i < a[node].size(); i++)
        {
            int next_node = a[node][i].first; // first값은 연결된 정점
            if (chk[next_node] == false) // 방문하지 않았으면
            {
                dist[next_node] = dist[node] + a[node][i].second; // 비용 저장
                q.push(next_node);
                chk[next_node] = true;
            }
        }
    }
}

void Input()
{
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        int x;
        cin >> x;

        int v = 0, d = 0;
        while (true)
        {
            cin >> v; if (v == -1) break;
            cin >> d;

            a[x].push_back(make_pair(v,d)); // a[i].first : i와 연결된 정점, a[i].second : 가중치
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);

    Input();

    BFS(1);

    int start = 1;
    for (int i = 2; i <= N; i++)
    {
        if (dist[i] > dist[start]) start = i;
    }

    BFS(start);

    int ans = dist[1];
    for (int i = 2; i <= N; i++)
    {
        if (ans < dist[i]) ans = dist[i];
    }

    cout << ans << "\n";

    return 0;
}