문제 이해 단계
https://www.acmicpc.net/problem/20924
노드의 개수 N과 루트 번호 R이 들어온다.
그리고 N-1개의 노드 정보가 주어지는데,
(a, b, c) -> a번 노드와 b번 노드가 연결되어 있는데 길이는 c이다.
그리고 기가 노드라는 것이 존재하는데,
이는 루트노드에서 시작했을 때 최초로 자식 노드가 2개 이상인 노드이다.
또는, 리프 노드가 단 1개인 경우엔 리프 노드인 동시에 기가 노드이다.
그리고 루트노드인 동시에 기가노드 또한 가능하다.
루트 노드 ~ 기가노드까지를 기둥이라고 하고
기가노드 ~ 임의의 루프노드를 가지라고 할 때,
기둥 길이의 합을 구하고, 가지 중 가장 길이가 긴 것을 출력해라.
문제 접근 단계
일단 조건부터 보면 노드는 최대 200,000개까지 들어올 수 있으며,
간선 길이는 최대 1,000까지이다.
200,000 * 1,000 = 2 * 10^8로
Int형을 넘지 않기 때문에 자료형은 신경 쓰지 않겠다.
문제의 유형을 유추해 보자면
대놓고 노드의 개수, 루트 노드, 길이라는 말을 난발했으므로 그래프 탐색문제이다.
관건은 문제에서 요구한 기가 노드를 찾아내는 것이다.
기가 노드를 기점으로 기둥과 가지를 분리해야 한다.
기가 노드는 루트 노드에서 시작했을 때
최초로 자식 노드를 2개 이상 가지는 것이다.
이를 그냥 단순히 연결된 개수로 생각해 보자.
만약 기가 노드가 루트노드가 아니라면 연결된 노드가 3개 이상이어야 한다.
왜냐하면 부모 노드 + (자식노드 2개 이상) 이어야 하니까
만약 기가 노드가 루트 노드라면
연결된 노드가 2개 이상이 어한다. 왜냐하면 부모노드는 없는 상태로
자식 노드만 2개 이상이어야 하기 때문이다.
루트 노드에서 시작해서 값을 더하다가
루트 노드를 제외하고 노드가 2개 이상 연결된 것이 나오면 탐색을 종료한다.
그리고 종료할 때 그 노드를 기가 노드로 지정한다.
그리고 그 기가 노드를 루트노드로 하여
모든 가지로의 탐색을 통해 최댓값을 구하면 된다.
최댓값을 구하는 것은 단순 BFS를 통해 값을 넘겨가는 것으로 가능하다.
자세한 것은 구현 단계에서 보겠다.
문제 구현 단계
// 연결된 노드의 정보
struct Node{
int node; // 연결된 노드
int len; // 길이
};
int gIdx = 0; // 기가 노드의 인덱스
vector<Node> v[200001];
bool visited[200001] = {false,}; //
// 기둥의 합을 구하는 함수
int getBody(int sx){
queue<int> q;
visited[sx] = true;
q.push(sx);
int result = 0;
while(!q.empty()){
int x = q.front();
q.pop();
// 루트 노드라면 2이상, 루트 노드가 아니라면 2초과
if(v[x].size() > 2 || (x == sx && v[x].size() >= 2)) {
gIdx = x;
return result;
}
// 연결된 노드로 이동하며 길이를 더해줌
for(int i = 0; i < v[x].size(); i++){
int nx = v[x][i].node;
int len = v[x][i].len;
if(visited[nx]) continue;
visited[nx] = true;
result += len;
q.push(nx);
}
}
return result;
}해당 부분에서 기둥 부분의 길이 합과, 기가 노드 인덱스를 구한다.
연결된 노드의 정보를 직관적으로 보기 위해 구조체 Node를 선언하였고,
gIdx에 기가노드의 인덱스를 저장한다.
기둥의 합을 구하는데에서 일반적인 BFS가 쓰인다.
길이를 result에 저장하는 과정을 반복한다.
단, 탐색을 하기 전에 해당 노드와 연결된 노드의 개수를 살펴봐서
해당 개수가 2개 초과이면 그 노드를 기가 노드로 선택하고 종료한다.
물론, 해당 노드가 루트노드일 때는 2개여도 기가 노드로 인정한다.
// 연결된 가지의 최댓값을 구하는 함수
void getLeaf(int sx){
queue<pair<int,int >> q;
visited[sx] = true;
q.push({sx,0});
while(!q.empty()){
int x = q.front().first;
int cnt = q.front().second;
q.pop();
for(int i = 0; i < v[x].size(); i++){
int nx = v[x][i].node;
int len = v[x][i].len;
if(visited[nx]) continue;
visited[nx] = true;
q.push({nx,cnt+len}); // 더한 값을 기억해 큐에 담아 넘김
max_val = max(max_val,cnt+len);
}
}
}다음은 찾은 기가노드의 인덱스를 토대로 가지까지의 합 중 최댓값을 찾는 getLeaf 함수이다.
매개변수로는 아까 찾은 gIdx의 인덱스 번호가 들어간다.
여기서는 큐에 pair로 2개의 값이 들어가는데,
이는 노드의 정보와 함께 누적된 합도 저장하기 위해서이다.
여기서도 쓰이는 것은 BFS인데, BFS가 가능한 이유는
한 너비씩 퍼져나가는 것이 각가지로 한 칸씩 전진하는 것이기 때문이다.
각가지로 한 칸씩 전진해서 더한 값을 각자 다른 큐에 저장해 두면
각기 다른 가지에 대한 합이 나오게 된다.
즉, 여기에 있던 값 중 최댓값이 결국 가지의 합 중 최댓값이 되는 것이다.
설명은 여기까지고 아래는 전체 함수를 올려두고 끝내겠다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N,R;
// 연결된 노드의 정보
struct Node{
int node; // 연결된 노드
int len; // 길이
};
int gIdx = 0; // 기가 노드의 인덱스
int max_val = 0; // 가지의 최댓값
vector<Node> v[200001];
bool visited[200001] = {false,}; //
// 기둥의 합을 구하는 함수
int getBody(int sx){
queue<int> q;
visited[sx] = true;
q.push(sx);
int result = 0;
while(!q.empty()){
int x = q.front();
q.pop();
// 루트 노드라면 2이상, 루트 노드가 아니라면 2초과
if(v[x].size() > 2 || (x == sx && v[x].size() >= 2)) {
gIdx = x;
return result;
}
// 연결된 노드로 이동하며 길이를 더해줌
for(int i = 0; i < v[x].size(); i++){
int nx = v[x][i].node;
int len = v[x][i].len;
if(visited[nx]) continue;
visited[nx] = true;
result += len;
q.push(nx);
}
}
return result;
}
// 연결된 가지의 최댓값을 구하는 함수
void getLeaf(int sx){
queue<pair<int,int >> q;
visited[sx] = true;
q.push({sx,0});
while(!q.empty()){
int x = q.front().first;
int cnt = q.front().second;
q.pop();
for(int i = 0; i < v[x].size(); i++){
int nx = v[x][i].node;
int len = v[x][i].len;
if(visited[nx]) continue;
visited[nx] = true;
q.push({nx,cnt+len}); // 더한 값을 기억해 큐에 담아 넘김
max_val = max(max_val,cnt+len);
}
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N >> R;
for(int i = 0; i < N-1; i++){
int v1,v2,v3;
cin >> v1 >> v2 >> v3;
v[v1].push_back({v2,v3});
v[v2].push_back({v1,v3});
}
if(N == 1) {
cout << "0 0";
return 0;
}
int body = getBody(R);
visited[gIdx] = false;
getLeaf(gIdx);
cout << body << " " << max_val;
}
시행착오
푸는 아이디어는 금방 생각해 내고, 맞췄다. 하지만 1시간 내로 푸는 것은 실패했다.
구현 능력이 부족해서인 것 같다.
기둥의 합을 구하는 것은 금방 했는데
마지막에 가지의 최댓값을 구하는 부분에서 애를 먹었다.
처음에는 DFS로 해보려고 했다가 계속 실패해서
찾아낸 방식이 저렇게 BFS를 돌리는 방식이었다.
좀 더 많은 문제를 풀어보자.
그래도 조금은 실력이 나아지는 것 같다.
생활비..