주유소( BOJ 28219 )

문제 : https://www.acmicpc.net/problem/28219

28219번: 주유소

 

문제 파악하기

N개의 마을에 필요한 주유소의 최소 개수를 구하는 문제입니다. N개의 마을은 (N-1)개의 도로로 연결되어 있으며, 길이가 K인 두 마을 사이의 경로에는 꼭 1개 이상의 주유소가 있어야 합니다. 문제 설명에서 (N-1)개의 도로로 연결되어 있으며, 모든 마을 사이의 경로는 유일하게 존재한다는 점을 통해 N개의 마을은 트리 형태로 연결되어 있음을 파악할 수 있습니다. 그리고 트리의 특징을 활용하면 필요한 주유소의 최소 개수 역시 구할 수 있습니다.

 

문제 해결하기

문제를 보면 길이가 K인 모든 경로에 1개 이상의 주유소가 필요합니다. 길이가 K인 경로를 찾는 방법은 마을을 2개씩 뽑는 방법도 있지만 N이 최대 200,000이기 때문에 좀 더 효율적인 방법이 필요합니다. 그렇다면 어떤 방법이 있을까요? 여기서 우리는 트리의 특징을 활용할 수 있습니다. 트리는 기본적으로 부모 노드와 자식 노드로 이루어집니다. 그리고 모든 경로는 자식 노드에서 시작해서 부모 노드로 올라갑니다. 그렇기에 우리는 맨 아래에 위치한 자식 노드인 말단 노드부터 시작해서 하나씩 올라가면서 경로를 살펴보고 주유소를 배치할지 말지를 결정할 수 있습니다.

 

그렇다면 현재 마을에 주유소를 설치할지 말지를 어떻게 판단할 수 있을까요? 이는 자식 노드들의 경로 길이를 살펴보면 알 수 있습니다. 우리는 자식 노드들이 거친 경로를 하나씩 살펴본 다음, 경로의 길이가 K 이상인 경우에 현재 마을에 주유소를 설치하면 됩니다. 만약 자식 노드가 하나라면 해당 자식 노드의 경로 길이가 K라면 주유소를 설치하고, 아니라면 현재 노드에 [ 자식 노드 길이 + 1 ]의 값을 기록하면 됩니다. 만약 자식 노드가 여러 개라면 경로의 길이가 가장 큰 2개를 뽑아 최대 경로의 길이를 확인하면 됩니다. 최대 경로의 길이는 [ 두 자식 노드의 길이 + 2 ]가 되며, 이 값이 K 이상이라면 현재 위치에 주유소를 설치하면 됩니다. 이처럼 주유소 설치를 최대한 미루면서 탐색하면 문제를 해결할 수 있습니다.

 

소스코드

#import <stdio.h>
#import <vector>
#import <algorithm>
#define NMAX 200010
using namespace std;
 
int N, K, a, b;
vector< int > graph[NMAX];
 
int check[NMAX];
vector< int > tree[NMAX];
 
int ret;
int dist[NMAX];
 
void make_tree(int idx) {
    for(int child:graph[idx]) {
        if(check[child]) continue;
 
        check[child] = 1;
        tree[idx].push_back(child);
 
        make_tree(child);
    }
}
 
void dfs(int cur) {
    int cnt=0;
    vector< int > chd;
 
    for(int child:tree[cur]) {
        dfs(child);
 
        dist[cur] = max( dist[cur], dist[child]+1 );
        chd.push_back(dist[child]);
    }
 
    sort(chd.rbegin(), chd.rend());
 
    if(chd.size() > 1) cnt = max( cnt, (chd[0]+1)+(chd[1]+1) );
    else if(chd.size() == 1) cnt = max( cnt, chd[0]+1 );
 
    if(cnt >= K) {
        ret++;
        dist[cur] = -1;
    }
}
 
int main() {
    // 입력
    scanf("%d %d", &N, &K);
    for(int i=1;i<N;i++) {
        scanf("%d %d", &a, &b);
 
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    // 트리 만들기
    check[1] = 1;
    make_tree(1);
 
    // 체크하기
    dfs(1);
 
    // 출력하기
    printf("%d", ret);
 
}
/*
5 2
1 2
2 3
3 4
4 5
ans: 1
 
7 2
1 2
1 3
2 4
2 5
4 6
7 4
ans: 2
*/

후기

트리 구조를 활용한 그리디 문제입니다. 정올 문제 치고는 추상화 과정이 부족했지만 트리 구조를 이해하는데 좋은 문제라고 생각합니다. 트리 구조를 배우고 연습하는 사람에게 추천하고 싶은 문제입니다.