백준 1240 노드사이의 거리 (c++) : 피너클

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

1240번: 노드사이의 거리

dfs를 이용한 문제다.

cin >> n >> m;
for (int i = 0; i < n - 1; i++) {
	int a, b, c;
	cin >> a >> b >> c;
	graph[a].push_back({ b, c });
	graph[b].push_back({ a, c });
}

값을 입력받은뒤 그래프를 양방향으로 연결해준다.

for (int i = 0; i < m; i++) {
	memset(visited, false, sizeof(visited));
	int a, b;
	cin >> a >> b;
	cout << dfs(a, b) << endl;
}

m번 반복하는 동안 계속 visited를 초기화 해주고 dfs를 통해 답을 출력한다.

int dfs(int now, int end) {
	if (now == end) return 0;
	visited[now] = true;
	int ans = 987654321;
	for (int i = 0; i < graph[now].size(); i++) {
		if (!visited[graph[now][i].first]) {
			ans = min(ans, graph[now][i].second + dfs(graph[now][i].first, end));
		}
	}
	return ans;
}

dfs함수는 현재 위치와 최종 목적지를 입력받는다.

만약 현재 위치가 최종 목적지라면 0을 리턴한다.

visited[now]를 true로 바꾼뒤 int ans를 선언한다. 만약 목적지로 가는 방법이 여러가지일때를 대비해 설정했다.

graph[now]에 연결된 모든 정점을 돌아보며 만약 아직 방문하지 않은 정점이라면

그 정점에 dfs를 해주고 ans를 업데이트한다.

그후 ans를 리턴한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

int n, m;
vector<pair<int, int>> graph[1001];
bool visited[1001];

int dfs(int now, int end) {
	if (now == end) return 0;
	visited[now] = true;
	int ans = 987654321;
	for (int i = 0; i < graph[now].size(); i++) {
		if (!visited[graph[now][i].first]) {
			ans = min(ans, graph[now][i].second + dfs(graph[now][i].first, end));
		}
	}
	return ans;
}

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

	cin >> n >> m;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b, c });
		graph[b].push_back({ a, c });
	}
	for (int i = 0; i < m; i++) {
		memset(visited, false, sizeof(visited));
		int a, b;
		cin >> a >> b;
		cout << dfs(a, b) << endl;
	}
}

전체코드다.