[G4] 백준 20924번 트리의 기둥과 가지 C++ 트리, DFS, 깊이 우선 탐색

리뷰

 

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

쉽게 보고 접근했던 문제인데 생각보다 처리해줘야 할 것이 많았다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• r : 루트 노드의 번호를 저장할 변수
• mn : 기가 노드 번호를 저장할 변수
• mpn : 기가 노드의 부모 노드 번호를 저장할 변수
• r_to_m : 루트부터 기가 노드까지의 거리를 저장할 변수
• mx_dist : 기가 노드로부터 리프 노드까지의 거리 최대값을 저장할 변수
• edges : 간선 정보를 저장할 pii타입 벡터 배열

 

함수

1. FindMiddleNodeAndDist

void FindMiddleNodeAndDist( int cn, int pn, int dist )
{
	if (
		edges[ cn ].size() >= 2 && cn == r ||
		edges[ cn ].size() >= 3 ||
		( edges[ cn ].size() == 1 && cn != r )
		)
	{
		mn = cn;
		mpn = pn;
		r_to_m = dist;
		return;
	}

	for ( const auto& [ nn, w ] : edges[ cn ] )
	{
		if ( nn == pn ) continue;
		FindMiddleNodeAndDist( nn, cn, dist + w );
	}
}

 

루트 노드로부터 기가 노드까지의 거리의 합과 기가 노드의 번호를 구하기 위한 함수

 

2. FindLongestDistToLeafNode

void FindLongestDistToLeafNode( int cn, int pn, int dist )
{
	if ( edges[ cn ].size() == 1 && cn != mn )
	{
		mx_dist = max( mx_dist, dist );
		return;
	}

	for ( const auto& [ nn, w ] : edges[ cn ] )
	{
		if ( nn == pn ) continue;
		FindLongestDistToLeafNode( nn, cn, dist + w );
	}
}

 

기가 노드로부터 리프 노드까지의 최대 길이를 구하기 위한 함수

 

 

문제풀이

1. n, r값을 입력 받고, n-1개의 간선 정보를 입력 받아 edges배열을 초기화한다.
2. FindMiddleNodeAndDist함수에 r, -1, 0을 전달하여 r_to_m와 mn, mpn을 초기화한다.
3. FindLongestDistToLeafNode함수에 mn, mpn, 0을 전달하여 mx_dist을 초기화한다.
4. r_to_m과 mx_dist를 공백을 기준으로 구분하여 출력한다.

 

트러블 슈팅

1. 간선이 부모->자식 순으로 들어올 것이라 가정하고 단방향 간선을 추가해 주어 WA를 받았다.
2. 루트 노드가 기가 노드인 경우를 체크해 주지 않아 WA를 받았다.
3. 기가 노드를 정확히 식별하고, 변수 mpn을 전역으로 선언해 FindLongestDistToLeafNode함수의 최초 호출부에 인자로 넘겨주어 루트 노드로 다시 타고 올라가는 경우를 막아 AC를 받았다.

 

참고 사항

1. 기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 2개 이상인 노드다.
2. 단, 리프 노드가 단 1개인 경우 리프 노드가 동시에 기가 노드가 된다.
3. 또한, 루트 노드가 동시에 기가 노드인 경우도 가능하다.

 

정답 코드

#include <iostream>
#include <vector>
using namespace std;
using pii = pair< int, uint16_t >;

const int N = 2e5 + 1;
int n, r, mn, mpn, r_to_m, mx_dist;
vector< pii > edges[ N ];

void FindMiddleNodeAndDist( int cn, int pn, int dist )
{
	if (
		edges[ cn ].size() >= 2 && cn == r ||
		edges[ cn ].size() >= 3 ||
		( edges[ cn ].size() == 1 && cn != r )
		)
	{
		mn = cn;
		mpn = pn;
		r_to_m = dist;
		return;
	}

	for ( const auto& [ nn, w ] : edges[ cn ] )
	{
		if ( nn == pn ) continue;
		FindMiddleNodeAndDist( nn, cn, dist + w );
	}
}

void FindLongestDistToLeafNode( int cn, int pn, int dist )
{
	if ( edges[ cn ].size() == 1 && cn != mn )
	{
		mx_dist = max( mx_dist, dist );
		return;
	}

	for ( const auto& [ nn, w ] : edges[ cn ] )
	{
		if ( nn == pn ) continue;
		FindLongestDistToLeafNode( nn, cn, dist + w );
	}
}

int main()
{
	ios::sync_with_stdio( 0 );
	cin.tie(0);

	cin >> n >> r;
	for ( int i = 0; i < n - 1; ++i )
	{
		int f, t; 
		uint16_t w;
		cin >> f >> t >> w;
		edges[ f ].push_back( { t, w } );
		edges[ t ].push_back( { f, w } );
	}

	FindMiddleNodeAndDist( r, -1, 0 );
	FindLongestDistToLeafNode( mn, mpn, 0 );
	//cout << mn << " ";
	cout << r_to_m << " " << mx_dist;
}