[백준/BOJ] 1967번: 트리의 지름( diameter ) - C++ 문제 풀이

 

문제 설명

 

 

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

 

풀이

이 문제는 주어진 트리에서 가장 긴 지름을 출력하는 문제입니다.

여기서, 트리의 지름이란 트리에서 임의의 두 노드 사이의 경로의 길이를 말합니다.

 

우선, 가장 긴 지름을 얻을 수 있는 두 노드는 모두 리프 노드임을 알아야 합니다.

리프( leaf ) 노드란 트리에서 가장 아래에 위치한 노드를 말합니다.

 

가장 간단한 트리를 가지고, 지름을 구하는 것부터 시작하겠습니다.

그리고, 간선의 가중치는 1로 가정합니다.

 

간단한 트리 구조

 

위의 이미지에서, 가장 긴 지름은 2 노드에서 루트( root ) 노드를 지나, 3 노드 도달하는 경로의 길이라는 것을 알 수 있습니다.

 

이를 리프 노드 관점으로 다르게 표현하면,

가장 긴 지름은 리프 노드에서 2 노드에 도달하는 경로로부터 루트 노드를 지나, 3 노드에서 리프 노드에 도달하는 경로의 길이가 될 것입니다.

 

그래서, 이 트리의 최장 지름은,

2 노드에 도달하는 경로 0 + 간선이 두 개 2 + 3 노드에서 리프에 도달하는 경로 0. 이렇게 해서 2가 됩니다.

 

좀 더 위의 트리를 확장해서 지름을 구해봅시다.

 

확장된 트리 구조

 

이제, 리프 노드에서 2 노드에 도달하는 경로의 길이는 더 이상 0이 아니라 1로 바뀌었습니다.

그리고, 3 노드에서 리프 노드에 도달하는 경로의 길이도 1이 되었습니다.

그래서, 이 트리의 최장 지름은,

2 노드에 도달하는 경로 1 + 간선이 두 개 2 + 3 노드에서 리프에 도달하는 경로 1. 이렇게 해서 4가 됩니다.

 

이 과정을 코드로 변경하는 일만 남았네요.

먼저, 문제의 입력으로부터 트리를 구성하면 다음과 같습니다.

#define SIZE    10000

typedef pair<int, int> VW;  // vertex-weight

vector<VW> tree[SIZE+1];	// 트리 구조

int N = readInt();	// 정점의 개수

int P, C, W;
for( int i = 0; i < N; i++){
    P = readInt();	// 부모 노드
    C = readInt();	// 자식 노드
    W = readInt();	// 간선의 가중치

    tree[P].push_back({C, W});	// 부모 노드에 연결된 자식 노드와 가중치 저장
}

 

그리고, 이 트리 구조를 사용하여, 위의 지름을 구하는 과정을 코드로 변경하면 다음과 같습니다.

int DFS( int v){	// 깊이 우선 탐색

    vector<int> hvec;
    
    for( const auto& x: tree[v]){	// 정점 v와 연결된 자식 정점 순환

        // 정점 x까지의 길이 + 간선 길이가 정점 v까지의 거리
        int height = DFS( x.first) + x.second;	
        hvec.push_back(height);
    } 

    int max_height = 0;	// 정점 v까지 도달하는데 가장 긴 경로의 길이

    if ( hvec.size() > 0){
        
        sort( hvec.begin(), hvec.end(), greater<int>() );	// 내림차순으로 정렬

        max_height = hvec[0];	// 정점 v까지 가장 긴 거리

        int dia = max_height;

	// 자식 노드가 2개 이상인 경우 
        // 정점 v를 지나 다른 자식 정점까지의 최장거리가 최장 지름
        if (hvec.size() > 1)	
            dia += hvec[1];	
        
        max_dia = max(dia, max_dia);
    }

    return max_height;	
}

이 함수는 깊이 우선 탐색 방법으로, 리프 노드까지 내려가 올라오면서, 각 노드까지 가장 긴 경로의 길이를 반환하는 함수입니다.

 

경로의 길이를 구하면서, 이 경로의 길이를 이용해, 자식의 노드 경로부터 부모 노드를 거쳐 다른 자식의 노드에 도달하는 최장 지름을 저장하고 있습니다.

지름은 두 노드 간의 길이이므로, 자식 노드가 3개 이상인 경우를 고려해서, 가장 긴 길이 2개를 사용해서 최장 지름을 구했습니다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
int ridx, nidx;

inline char read() {
	if (ridx == nidx) {
		nidx = fread(rbuf, 1, 1 << 20, stdin);
		if (!nidx) return 0;
		ridx = 0;
	}
	return rbuf[ridx++];
}
inline int readInt() {
	int sum = 0;
	char now = read();
	bool flg = false;

	while (now <= 32) now = read();
	if (now == '-') flg = true, now = read();
	while (now >= 48) sum = sum * 10 + now - '0', now = read();

	return flg ? -sum : sum;
}
//----------------------------------------------------------

#define SIZE    10000

typedef pair<int, int> VW;  // vertex-weight

vector<VW> tree[SIZE+1];

int max_dia = 0;

int DFS( int v){

    vector<int> hvec;

    for( const auto& x: tree[v]){

        int height = DFS( x.first) + x.second;
        hvec.push_back(height);
    } 

    int max_height = 0;

    if ( hvec.size() > 0){
        
        sort( hvec.begin(), hvec.end(), greater<int>() );

        max_height = hvec[0];

        int dia = max_height;

        if (hvec.size() > 1)
            dia += hvec[1];
        
        max_dia = max(dia, max_dia);
    }

    return max_height;
}

int main(){

    int N = readInt();

    int P, C, W;
    for( int i = 0; i < N; i++){
        P = readInt();
        C = readInt();
        W = readInt();

        tree[P].push_back({C, W});
    }

    DFS(1);

    printf("%d", max_dia);

    return 0;
}