백준 1240 _ 노드사이의 거리

www.acmicpc.net/problem/1240

1240번: 노드사이의 거리

---

✨ 내 소스 코드

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


vector<pair<int, int> > tree[1001];
int Distance[1001][1001];
int Visited[1001];


void dfs(int start, int k, int len) {

	Distance[start][k] = len;
	int size = tree[k].size();
    
	for (int i = 0; i < size; i++) {
		int route = tree[k][i].first;
		int cost = tree[k][i].second;
        
		if (!Visited[route])
		{
			Visited[route] = 1;
			dfs(start, route, len + cost);
			Visited[route] = 0;
		}
	}
}


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	int N, M, a,b,len;
	cin >> N >> M;
    
	for (int i = 0; i < N - 1; i++) {
		cin >> a >> b >> len;
		tree[a].push_back({ b,len });
		tree[b].push_back({ a,len });
	}
    
	for (int i = 1; i <= N; ++i)
	{
		Visited[i] = 1;
		dfs(i, i, 0);
		Visited[i] = 0;
	}
    
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		cout << Distance[a][b]<<'\n';
	}

	return 0;
}

 

🙏 문제 풀이

bfs로도 풀 수 있다는데, 나는 왜인지 dfs가 더 편해서 dfs로 풀게 되었다

나중에 bfs로도 다시 풀어보면 좋을 것 같다

 

⭐ 문제 풀이 결과