그래프탐색 DFS을 이용해 경로의 길이를 더하고, 리턴조건 달성 시 (도착점 도달 시) 경로에서 최대 간선의 길이를 뺀 값 중 최솟값이 답이다. DFS 함수 구현 자체는 간단하다.
내가 이 문제를 풀며 헷갈렸던 것은 <각 간선의 길이 정보를 어떻게 저장할 것인가?> 였다. 연결된 노드 정보를 벡터에 저장할 수 있지만, 추가적으로 길이 정보를 저장하기 위해선 메모리가 초과되는 2차원 배열을 선언해야 할 것 같았다.
2차원 배열을 따로 선언하는 대신 pair을 이용했다.
pair
- 헤더 : utility
- 선언 : pair<자료형, 자료형> ex) pair<int, string> p
- 입력 : make_pair(1, abc)
- 값 찾기 : pair.first = 1, pair.second = abc
- sort : 첫 번째 인자(pair.first) 기준 정렬, 첫 번째 인자 같을 경우 두 번째 인자 기준 정렬
auto
- 타입 추론, 데이터 추론
- 초기화 값에 따라 알아서 데이터 타입을 정해주는 키워드
- for(auto x : adj[now]) -> x를 pair로 추론, 반복문 돌림
#include <iostream>
#include <utility> //pair
#include <vector> //vector
#include <algorithm> //max함수
using namespace std;
vector<pair<int,int>>[100001];
int n, s, e, a, b, l, ans = 100000000;
int chk[100001]; //방문처리 체크 배열
void dfs(int now, int d, int mx){
//now : 현재 노드 d : 경로 길이 mx : 최대 간선 길이
if(now == e){ // 도착점 도달 시
if(d-mx < ans) ans = d - mx;
// 새로 리턴된 경로가 최소값이면 ans(최종 정답) 새로 정의
return;
}
chk[now] = 1; //방문처리
for(auto x : adj){ //auto :
if(!chk[x.first]) dfs(x.first, d+x.second, max(mx, x.second));
//x.first = now의 연결된 노드 (다음 노드)
//다음 노드에 방문하지 않았을 경우 다음 노드에 대해 dfs
//d += now와 x.first 사이 간선 길이
//최대 간선 길이 새로 정의
}
}
int main(void){
scanf("%d %d %d", &n, &s, &e);
for(int i = 0; i< n-1; i++){
scanf("%d %d %d", &a, &b, &l);
adj[a].push_back(make_pair(b, l));
adj[b].push_back(make_pair(a, l)); //입력
}
dfs(s); //dfs(시작점)
printf("%d", ans);
return 0;
}