[백준 1772] 정원 정리

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

1772번: 정원 정리

 

우연히 접하게된 문제였다. 문제는 꽤나 간단했지만 생각 좀 해야 했다. 굳이 블로그에 정리하는 이유는 한 가지 패턴 아닌 패턴을 발견해서 기뻐서 정리할까 한다.

 문제 상에서 보면 노드 N개와 간선 N-1개의 연결 그래프라고 하는데 이 말인 즉, 이 그래프는 트리라는 걸 의미한다. 내가 이번에 찾게된 문제 풀이 패턴은 트리 문제를 볼 때마다 dfs, bfs ... 뭐 이런게 많겠지만, 규칙 찾기가 어렵다 싶은 문제들은 순회를 해서 한 번 펼쳐놔 봐야 한다. 전위?중위?후위? 많겠지만 중위는 이진트리 아니면 쓸모 없으니 전위, 후위만 놓고 보면 두 개 다 해보고 규칙 안나온다 싶으면 전위+후위를 해보면 된다.

 예제입력을 보면 아래와 같은 트리가 나온다.

이걸 전위+후위 순회를 해서 vector에 정리하면 다음과 같다.

1 -> 2 -> 6 -> 6-> 7 -> 7 -> 8 -> 8-> 2-> 3-> 3 -> 4-> 9 -> 9 -> 10 -> 10 -> 11-> 11-> 4 -> 5 -> 5 -> 1

즉, 자기 노드로 들어올때 한 번, 자기 자식 싹다 돌고 나오면 다시 한번. 이렇게 되면 자기 자신이 다시 등장하는 구간은 싹다 자기 자식의 개수를 의미하게 된다. 1번 노드나 2번 노드를 보면 알수 있고 leaf노드들의 경우는 자기 자신 사이에는 아무런 노드가 오지 않는 것 또한 볼 수 있다.

 

 이제 가지 자르기를 잘 생각해보면, A 노드와 A 노드의 자식들을 1)포함하거나 2) A노드는 포함하고 자식 들 중에서 잘라내거나 하는 방식이다. 마치 현재 idx가 가리키는 노드의 짝꿍으로 jmp 하거나 다음 idx를 탐색하면 된다. 하지만 한가지 유의할 점은 jmp 즉, 잘라내기를 했을 때, 잘라낸 나무와 잘려 나간 나무 둘 다 가지치기 목록에 포함된다.

 어떻게 하면 좋을까? 간단하게 이렇게 봐도 좋다. 전위+후위 순회를 해서 만든 vector에서 현재 위치와 끝 지점을 정해 놓고 그 구간에서 목표로 하는 노드의 수를 만드는데 최소 몇번의 잘려나감이 존재했는지를 파악하고 기록해 놓는 것이다.

 그렇기에 현재 노드에서 목표를 달성하는 방법 3가지 중에서 어떤 방식을 선택했을 때 최적인지 그리고 만약 구하고 싶어하는 구간이 이미 구한 구간이라면 기록에서 꺼내놓는 즉 dp로 해결해보자

 

그렇게 코드는 아래와 같게 된다. 코드를 기준으로 설명해보자.

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

const int INF = 987654321;

int cache[301][301][150];
vector<int> nodes;
int jmp[151];
vector<vector<int>> adj;
bool visited[151];
int N, M;

int cutting(int cur, int sum, int end){
    if(cur > end) return INF;
    if(cur == end){
        if(sum == M)return 0;
        else return INF;
    }
    
    int& ret = cache[cur][end][sum];
    if(ret != -1)return ret;
    
    int leaf = nodes[cur];
    if(jmp[leaf] == cur){
        return ret = cutting(cur+1,sum,end);
    }
    ret = INF;

    ret = min(ret,cutting(jmp[leaf]+1, sum,end)+1);
    ret = min(ret,cutting(cur+1, sum+1,end));
    ret = min(ret,cutting(cur,0,jmp[leaf])+1);
    return ret;
}

void makeSeq(int cur){
    nodes.push_back(cur);
    visited[cur] = true;
    bool flag = false;
    for(auto& e : adj[cur]){
        if(visited[e])continue;
        makeSeq(e);
        flag = true;
    }
    
    nodes.push_back(cur);
    jmp[cur] = nodes.size()-1;
}

int main(){
    
    memset(cache,-1,sizeof(cache));
    cin >> N >> M;
    
    adj.resize(N+1);
    
    for(int i=1;i<N;i++){
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    makeSeq(1);
    N = nodes.size();
    
    int ret =cutting(0, 0,N);
    
    if(N == 1){
        if(M == 1)cout << 0 << endl;
        else cout << -1 << endl;
        return 0;
    }
    
    if(ret >= INF)cout << -1 << endl;
    else cout << ret << endl;
    return 0;
}

 

 makeSeq()의 코드 중에서 jmp배열을 보면 전위 순회에서 찾게된 노드의 반대편(후위) 노드의 위치를 새겨 놓는다.

 이를 통해  cutting dp를 돌릴 때 현재 위치가 후위 순회해서 생긴 노드를 가리키고 있다면 다음 노드를 가리키게 한다. 만약 후위 순회해서 생긴 노드가 아닐 경우 1. 후위 노드 + 1 위치로 jmp 2. 현재 노드를 포함하고 가기 3. 현재 노드 부터 후위 노드 구간에서 cutting dp를 수행하게끔 했다. 이때 dp에 대한 정보는 현재 위치, 종료점, 포함된 노드의 개수가 필요해지고 현재 노드가 끝까지 도착 했는데 목표한 M값과 포함한 노드의 수와 같다면 return 0를 하여 재귀를 탈출탈출 하면서 1씩 쌓이게 했다.

 

끝!