[백준] 13016번 : 내 왼손에는 흑염룡이 잠들어 있다

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 트리 자료구조 형식의 문제로, 도시가 n개일 때 도로가 n-1개 이고, from과 to가 같을 수 없다는 조건(사이클 X, self-loop X)을 볼 때 트리의 특징임을 알 수 있다. 또한 어떤 임의의 정점에서 가장 먼 정점을 구하는 문제이기 때문에 트리의 지름을 이용하여 풀어야 한다.

1) 각 도시들에 대한 pair(인접한 도시, 도시 간의 거리)들의 벡터를 저장하는 벡터 cities, 임의 정점에서부터 다른 도시들까지의 거리를 저장하는 벡터 dist를 선언한다.

2) 데이터를 입력 받아 각 도시들에 어떤 도시가 인접해있는지, 그 도시와 거리는 얼마인지 cities에 저장한다.

3) 임의의 정점(도시)에서 시작하는 DFS를 실행해 해당 정점에서 가장 먼 정점을 찾아 vertex1에 저장한다.

• DFS 함수의 맨 첫 부분에서 매개변수를 통해 입력 받은 거리를 dist[현재 도시]에 저장한다.
• dist[현재 도시]를 지금까지의 최대 거리와 비교해 더 클 경우 최대 거리를 dist[현재 도시]로 갱신한다. 이 때의 도시 번호도 저장해둔다.
• cities에 저장되어있던 인접 도시들에 대해 아직 방문한 적 없는 도시일 경우 해당 도시에서부터 다시 DFS를 재귀 실행한다. 이때 현재 도시까지 이동한 거리를 넘겨준다.

4) vertex1에서 시작하는 DFS를 실행해 해당 정점에서 가장 먼 정점을 찾아 vertex2에 저장하고, vertex1에서 다른 정점들까지 거리를 전부 dist에 저장하고, dist_v1에 옮겨담는다.

5) vertex2에서 시작하는 DFS를 실행해 해당 정점에서 다른 정점들까지 거리를 전부 dist에 저장한다.

6) 각 도시에서 vertex1 까지의 거리와 vertex2 까지의 거리를 비교해 더 먼 거리를 출력한다.

🖥️ 풀이 코드

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

using namespace std;
typedef pair<int, int> pii;

vector<vector<pii>> cities;	// 각 도시들에 대한 pair(인접한 도시, 도시 간의 거리)들의 벡터를 저장하는 벡터
vector<int> dist;			// 임의 정점에서부터 다른 도시들까지의 거리
int dist_v1[50001];			// vertex1에서부터 다른 도시들까지의 거리
int dist_v2[50001];			// vertex2에서부터 다른 도시들까지의 거리
int maxDistance;			// 임의 정점에서 가장 먼 도시에 갔을 때의 거리
int farCity;				// 임의의 정점에서 가장 먼 도시

void DFS(int distance, int currentCity)
{
	dist[currentCity] = distance;	// 도시가 n개일 때 경로가 n - 1개 밖에 없기 때문에 한 도시로 가는 경로는 한 가지 밖에 없음.
	if (dist[currentCity] > maxDistance)
	{
		maxDistance = distance;
		farCity = currentCity;
	}

	for (int i = 0; i < cities[currentCity].size(); i++)
	{
		int nearCity = cities[currentCity][i].first;
		
		if (dist[nearCity] == 50000)
			DFS(distance + cities[currentCity][i].second, nearCity);
	}
}

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

	int n;
	cin >> n;

	cities.resize(n);
	dist.assign(n, 50000);

	for (int i = 0; i < n - 1; i++)
	{
		int from, to, length;
		cin >> from >> to >> length;
		
		// 도로는 양쪽 연결되어있으므로 from 도시의 인접 도시에 to를 넣고, to 도시의 인접 도시에 from을 넣는다.
		cities[from - 1].push_back(pii(to - 1, length));
		cities[to - 1].push_back(pii(from - 1, length));
	}

	// 임의의 정점(도시) 하나에서 시작하여 DFS 실행해 해당 정점에서 가장 먼 정점 찾아 vertex1에 저장
	DFS(0, 0);
	int vertex1 = farCity;

	dist.assign(n, 50000);
	maxDistance = 0;
	// vertex1에서 시작하여 DFS 실행해 가장 먼 정점 찾아 vertex2에 저장 및 각 도시까지의 거리 구해 dist_v1에 저장
	DFS(0, vertex1);
	int vertex2 = farCity;

	for(int i = 0; i < dist.size(); i++)
		dist_v1[i] = dist[i];

	dist.assign(n, 50000);
	maxDistance = 0;
	// vertex2에서 시작하여 DFS 실행해 각 도시까지의 거리 구해 dist에 저장
	DFS(0, vertex2);
	
	for (int i = 0; i < n; i++)
		cout << (dist_v1[i] > dist[i] ? dist_v1[i] : dist[i]) << endl;
}

🖥️ 개선 전 코드

처음에는 아래 코드에 주석 처리된 부분과 같이 방문 여부를 visited 배열을 따로 만들어서 체크 해줬다. 그런데 이렇게 따로 배열을 마련할 필요 없이 dist에 미리 쓰레기값을 넣어 놓고 dist의 값이 쓰레기값인지, 입력된 값인지 확인하면 해당 도시의 방문 여부를 확인할 수 있다. (해당 도시를 방문하면 dist의 값이 시작 도시와의 거리로 갱신되기 때문)

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

using namespace std;
typedef pair<int, int> pii;

vector<vector<pii>> cities;	// 각 도시들에 대한 pair(인접한 도시, 도시 간의 거리)들의 벡터를 저장하는 벡터
//bool visited[50001];		// 각 도시들의 방문 여부 체크
vector<int> dist;			// 임의 정점에서부터 다른 도시들까지의 거리
int dist_v1[50001];			// vertex1에서부터 다른 도시들까지의 거리
int dist_v2[50001];			// vertex2에서부터 다른 도시들까지의 거리
int maxDistance;			// 임의 정점에서 가장 먼 도시에 갔을 때의 거리
int farCity;				// 임의의 정점에서 가장 먼 도시

void DFS(int distance, int currentCity)
{
	dist[currentCity] = distance;	// 도시가 n개일 때 경로가 n - 1개 밖에 없기 때문에 한 도시로 가는 경로는 한 가지 밖에 없음.
	if (dist[currentCity] > maxDistance)
	{
		maxDistance = distance;
		farCity = currentCity;
	}

	for (int i = 0; i < cities[currentCity].size(); i++)
	{
		int nearCity = cities[currentCity][i].first;
		
		if (dist[nearCity] == 50000)
		{
			//visited[nearCity] = true; 
			DFS(distance + cities[currentCity][i].second, nearCity);
			//visited[nearCity] = false;
		}
	}
}

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

	int n;
	cin >> n;

	cities.resize(n);
	dist.assign(n, 50000);

	for (int i = 0; i < n - 1; i++)
	{
		int from, to, length;
		cin >> from >> to >> length;
		
		// 도로는 양쪽 연결되어있으므로 from 도시의 인접 도시에 to를 넣고, to 도시의 인접 도시에 from을 넣는다.
		cities[from - 1].push_back(pii(to - 1, length));
		cities[to - 1].push_back(pii(from - 1, length));
	}

	// 임의의 정점(도시) 하나에서 시작하여 DFS 실행해 해당 정점에서 가장 먼 정점 찾아 vertex1에 저장
	//visited[0] = true;
	DFS(0, 0);
	//visited[0] = false;
	int vertex1 = farCity;

	dist.assign(n, 50000);
	maxDistance = 0;
	// vertex1에서 시작하여 DFS 실행해 가장 먼 정점 찾아 vertex2에 저장 및 각 도시까지의 거리 구해 dist_v1에 저장
	//visited[vertex1] = true;
	DFS(0, vertex1);
	//visited[vertex1] = false;
	int vertex2 = farCity;

	for(int i = 0; i < dist.size(); i++)
		dist_v1[i] = dist[i];

	dist.assign(n, 50000);
	maxDistance = 0;
	// vertex2에서 시작하여 DFS 실행해 각 도시까지의 거리 구해 dist에 저장
	//visited[vertex2] = true;
	DFS(0, vertex2);
	//visited[vertex2] = false;
	
	for (int i = 0; i < n; i++)
		cout << (dist_v1[i] > dist[i] ? dist_v1[i] : dist[i]) << endl;
}