BOJ 3851. Jumping monkey

 문제 링크

 

문제 풀이

 어떤 정점 $n\leq 21$개, 간선 $m$개의 그래프 위에 원숭이가 살고 있고, 매 턴마다 인접한 정점으로 항상 움직인다. 이때 매턴마다 그래프 위에 정점 하나를 골랐을 때 최악의 경우에도 언젠가는 원숭이를 잡을 수 있는지를 묻는 문제이다. 또 잡을 때까지의 최소 몇 번의 턴이 필요한지와 가능한 실례도 제시해야한다. 

 

 일단 문제를 보자마자 생각할 수 있는 것은 가능하기 위해서는 당연하게 이 그래프가 사이클이 없는 트리여야한다는 것이다. 만약 사이클이 있다면 그 사이클 위에 있는 원숭이는 매턴마다 두 가지의 선택지가 반드시 존재하므로 원숭이를 유인할 수 없다. 이는 직관적으로도 자명하다. 따라서 $m$이 $n-1$이 아닐 경우에는 볼 필요가 없어진다.

 

 처음에는 트리인 경우는 모두 가능하다고 생각했다. 하지만 아래 그림처럼 갈래가 '좀' 있는 트리들의 경우 17과 같은 정점을 탐색한 이후에 원숭이가 15나 2에 있다가 이전에 탐색했던 곳들로 넘어가버리면 그 곳들은 탐색했던 의미가 없어지므로 원숭이가 존재가능한 정점들의 개수를 줄이지 못하게 된다.

 조금 더 엄밀하게 말하면 현재 상태에서 17을 기준으로 2방향 서브트리들을 모두 탐색했다고 가정하고, 트리를 이색 컬러링했을 때 원숭이가 17과 같은 색깔을 가진 정점 위에 있다고 가정할 때 다음 턴에 17에서 15방향의 서브트리를 탐색하든 16방향의 서브트리를 탐색하든 원숭이가 그 반대 서브트리에 있었다면 다시 2방향 서브트리로 가거나 그대로 있을 수 있기 때문에 16방향 서브트리를 모두 탐색하고 17으로 돌아왔더라도, 2방향 서브트리에도 원숭이가 존재할 수 있게 되었으므로 아무일도 일어나지 않을 것과 같아진다.

 따라서 우리가 관심 있는 트리는 아래와 같이 적당히 선형적 $($?$)$으로 생긴 트리들이다. 

여기서 어떤 트리에 대해 '선형적' 으로 생겼다는 것은 모든 정점 $v \in V(G)$에 대해 다음 조건이 만족되어야한다.

• $v$와 인접한 모든 노드 $u$중, $u$가 리프노드 혹은 리프노드만을 자식으로 갖는 노드가 아닌 $u$의 개수가 2개 이하이다.

아래의 트리들도 이런 조건을 만족한다.

 이제 이런 트리들에 대해서 탐색을 진행해주면 된다. 어떻게 탐색을 해야할지를 생각해보면 그래프를 이색 컬러링을 하였을 때 현재 탐색 위치랑 원숭이의 색깔이 다르다면 아무리 계속 인접한 영역을 탐색한다하더라도 찾을 수 없다.

절대 만날 수 없는 케이스

 이를 통해서 최악의 상황을 대비해 각각의 색을 모두 탐색해야한다는 결론을 얻을 수 있다. 그리고 이를 Phase1, Phase2라고 하자. 최악의 경우에는 Phase1에서 처음에 탐색을 시작한 색과 초기에 원숭이가 다른 색에 있었을 것이므로 Phase2에서 원숭이를 잡게 될 것이다. 

 만약 원숭이의 현재색깔과 탐색 위치의색깔이 같은 잡을 수 있는 상태라면 리프노드는 탐색을 안해봐도 되는 것이 자명한게 리프노드의 부모노드와 리프노드는 색이 다르므로 리프노드의 부모노드를 탐색하고 있는 중이라면 원숭이는 리프노드에 존재할 일이 없을 것이다. 색깔이 다르다면 이건 더 당연하게 잡지 못하므로 모든 경우에서 리프노드는 고려하지 않는다.

 

$C(v) := (v$에서 시작해 리프노드를 제외한 모든 정점을 방문하는데 필요한 최소비용$)$ 라고 하자. $($단 $v$는 리프노드가 아님$)$ 그러면 문제에서 주어진 트리에 대해 시행해야하는 최소 횟수는 아래의 값과 동일해진다. 

$$2\times\left\{\min_{v\in V(G),\space d(v)>1}{C(v)}\right\} $$

 여기서 2를 곱한 것은 최소이려면 Phase1과 Phase2에서 모두 최소인 경우이고 이 경우에 대한 $C(v)$는 동일할 것이기 때문에 곱하였다. 그럼 이제 $C(v)$값과 이때의 경로만 잘 구해주면 된다. 이는 dfs로 쉽게 할 수 있다. 이보다 더 중요한 것은 문제에 나와있는대로 경로가 여러개 존재할 때 사전 순서대로 처리해주는 작업이다. 만약 Phase1에서 $v$로 시작해서 탐색하였을 때 경로의 길이가 최소이고, 이가 짝수라면 Phase2에서는 $v$와 색깔이 다른 정점 $u$에서 시작해야하고, $C(v) = C(u)$이며 $v,u$모두 이를 만족하는 정점들 중 정점의 번호가 최솟값이어야한다. 반대로 경로의 길이가 홀수라면 Phase2에서 $v$와 색깔이 같은 정점 $u$로 시작해야하며 마찬가지로 $C(v) = C(u)$일텐데 $v$가 $C(v)$가 최소인 정점들 중 그 번호가 최소이므로 $u = v$가 될 것이다.

 

 이를 정리해보면 다음과 같다.

• 그래프에 cycle이 존재하는 경우 불가능. $\Leftrightarrow m \neq n-1$에서 불가능.
• $\forall v \in V(G), U := \left\{u\space|\space u\in Adj(v), u\notin LeafNode(G)\wedge(^\exists w = Adj(u)\space s.t. w\neq v, w\notin LeafNode(G)) \right\}$일 때 $n(U) \leq 2$가 아니라면 불가능.
• $2\times\left\{\min_{v\in V(G),\space d(v)>1}{C(v)}\right\} $ 만큼이 시행이 최소임.
• 위에서 찾은 $v$에 대해 $C(u) = C(v)$를 만족하는 $u$들의 번호 크기와 $v$와 색깔을 이용해 Phase2에서 시작할 정점 선택후 출력

 

코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
const int nmax = 21;
typedef vector<int> vi;

int n,m;
vector<int> graph[nmax + 10];

bool isLeaf(int child){
    if(graph[child].size() == 1) return true;
    return false;
}

vector<int> insertVector(vi v1, vi v2, bool inv){
    if(inv){
        for(int i=v2.size()-2;i>=0;i--){
            v1.push_back(v2[i]);
        }
    } else {
        for(int i=0;i<v2.size();i++){
            v1.push_back(v2[i]);
        }
    }
    
    return v1;
}

vi dfs(int st, int bf){
    bool flag = true;
    int mx = 0, sum = 0, mx_u;
    vi path;
    path.push_back(st);
    for(int u=0;u<graph[st].size();u++){
        int nv = graph[st][u];
        if(isLeaf(nv) || nv == bf) continue;
        flag = false;
        vi df = dfs(nv,st);
        if(mx <= df.size()){
            mx = df.size();
            mx_u  = u;
        }
    }
    if(flag) return path;
    
    for(int u=0;u<graph[st].size();u++){
        int nv = graph[st][u];
        if(isLeaf(nv) || nv == bf || u == mx_u) continue;
        vi df = dfs(nv,st);
        path = insertVector(path, df, false);
        path = insertVector(path, df, true);
        path.push_back(st);
    }
    vi df = dfs(graph[st][mx_u],st);
    path = insertVector(path, df, false);
    
    return path; 
}

void solve(){
    if(n == 1) {
        cout<<"1: 0"<<"\n"; return;
    } else if(n == 2){
        cout<<"2: 0 0"<<"\n"; return;
    }
    
    for(int i=0;i<n;i++) sort(graph[i].begin(),graph[i].end());
    
    int ans = 1e9;
    vi minPath, stPoints;
    vector<vi> paths;
    for(int v=0;v<n;v++){
        if(graph[v].size() <= 1) continue;
        vi p = dfs(v,-1);
        if(2*p.size() < ans){
            ans = 2*p.size();
            minPath = p;
            stPoints.clear();
            paths.clear();
        }
        if(2*p.size() == ans) {
            stPoints.push_back(v);
            paths.push_back(p);
        }
    }
    
    cout<<ans<<": ";
    for(int i=0;i<minPath.size();i++) cout<<minPath[i]<<" ";
    if(minPath.size() % 2 == 0) {
        bool hasSameColor[nmax + 10];
        hasSameColor[stPoints[0]] = true;
        queue<pair<int,int>> q;
        q.push({stPoints[0],-1});
        while(!q.empty()){
            int v = q.front().first, bv = q.front().second;
            q.pop();
            if(bv != -1) hasSameColor[v] = !hasSameColor[bv];
            for(int i=0;i<graph[v].size();i++){
                int nv = graph[v][i];
                if(nv == bv) continue;
                q.push({nv,v});
            }
        }
        int nxPointIdx;
        for(int i=1;i<stPoints.size();i++){
            if(!hasSameColor[stPoints[i]]){
                nxPointIdx = i;
                break;
            }
        }
        
        for(int i=0;i<paths[nxPointIdx].size();i++) cout<<paths[nxPointIdx][i]<<" ";
    }
    else for(int i=0;i<minPath.size();i++) cout<<minPath[i]<<" ";
    
    cout<<"\n";
}


bool isImpossible(){
    int cnt1 = 0;
    for(int i=0;i<n;i++){
        int cnt2 = 0;
        for(int j=0;j<graph[i].size();j++){
            int nv = graph[i][j];
            for(int k=0;k<graph[nv].size();k++){
                if(graph[nv][k] == i) continue; 
                if(!isLeaf(graph[nv][k])){
                    cnt2 ++;
                    break;
                }
            }
        }
        if(cnt2 >= 3) return true;
    }
    return false;
}

int main(){
    fastio;
    while(true){
        cin>>n>>m; if(!n && !m) exit(0);
        for(int i=0;i<n;i++) graph[i].clear();
        for(int i=0;i<m;i++){
            int u, v; cin>>u>>v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        if(m != n-1 || isImpossible()) cout<<"Impossible"<<'\n';
        else solve();
    }
}