[백준/C++] 1240 노드사이의 거리

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

 

코드

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

typedef long long ll;

vector<vector<pair<int, ll>>> tree;
ll ans = LLONG_MAX;
vector<bool> visit(1001);

void find_node(int now, int target, ll tmp) {
	if (now == target) {
		ans = min(ans, tmp);
		return;
	}
	else {
		visit[now] = true;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i].first;
			int cost = tree[now][i].second;
			if (!visit[next]) {
				visit[next] = true;
				find_node(next, target, tmp + cost);
			}
		}
	}
}

int main() {
	int n, m, target, now;
	cin >> n >> m;

	tree.resize(n+1);

	for (int i = 0, a, b, len; i < n - 1; i++) {
		cin >> a >> b >> len;

		tree[a].push_back({ b, len });
		tree[b].push_back({ a, len });
	}

	while (m--) {
		ans = LLONG_MAX;
		fill(visit.begin(), visit.end(), false);

		cin >>  now >>  target;
		find_node(now, target, 0);
		cout << ans << "\n";
	}

	return 0;
}

 

설명

n, m 정보를 받고 트리 정보를 저장한다. 이때 tree[a].push({b, len}) 형태를 이용했는데, a 노드에서 b 노드로 갈 수 있고, 두 노드 간 거리는 len 이라는 의미이다.

 

이후 두 노드 정보를 받고 find_node() 함수를 호출해서 거리를 구한다. 매번 방문 배열과 결과값을 초기화해주고 시작해야 한다. find_node 함수에서는 dfs를 수행한다. 이때 tmp 값에 계속 이동한 거리를 업데이트한다.

 

느낀 점

문제를 읽고 바로 트리 구성 후  dfs를 돌려주면서 해결했다! 한 번에 맞았다.