[c++] 백준 24232 망가진 나무

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

24232번: 망가진 나무

방향을 가진 그래프가 주어진다. 방향성을 없애면 트리가 된다는 특징이 있다.

임의의 한 정점에서 다른 모든 정점으로 갈 수 있게 하려면

간선의 방향을 바꿔주어야 하는데, 이때 방향을 바꾸어야 하는 최솟값을 구하는 문제이다.

 

이 문제를 풀려면 모든 정점에 대해 방향을 바꿔주어야 하는 횟수 (이하 비용으로 대체하겠다)를

알아야 할 필요가 있다.

그러려면 모든 정점 n개에 대해 dfs를 진행하면 대략적으로 시간복잡도가 O(n^2)이므로

이 문제를 해결할 수 없다.

 

따라서 이 문제를 해결하기 위한 중요한 아이디어는

한 정점에 대한 비용을 구해놓으면 다른 정점에 대한 비용도 구하기 쉽다는 것이다.

 

이 문제를 풀 때 나는 dfs 세 번을 사용하여 풀었다.

 

첫 번째 dfs에서는 임의의 한 정점에서 모든 정점으로 가기 위한 비용을 구한다.

두 번째 dfs에서는 간선을 통해 이동하면서 다른 정점에 대한 비용을 구한다.

세 번째 dfs에서는 어떤 간선의 방향을 바꾸어야 하는지를 구한다.

 

그래서 다른 정점에서의 비용을 구하는 아이디어가 무엇인가

잘 생각해 보면 이는 dp문제의 특징을 띄고 있다는 것을 눈치챌 수 있다.

 

만약 현재 정점 cur에서의 비용이 cost라고 하면,

다음 정점 next에 대한 비용은 다음과 같다.

 

1. cur과 next의 관계가 순방향일 경우

next에서의 비용은 cost+1이 된다.

 

2. cur과 next의 관계가 역방향일 경우

next에서의 비용은 cost-1이 된다.

 

이 원리가 성립하는 이유는 a정점에서 b정점으로 이동할 때,

a와 b를 잇는 간선을 제외한 다른 간선들은 a에 대한 방향성과 b에 대한 방향성이 같고,

a와 b를 잇는 간선만이 방향성이 달라지기 때문이다.

 

문제의 예제를 통해 이해해 보자

정점 2에서의 비용이 정점 3에서의 비용-1인 모습이다.

정점 1에서의 비용이 정점 3에서의 비용+1인 모습이다.

 

+) 그래프 입력받을 때

    그래프를 입력받을 때, a에서 b로 가는 입력을 받았다면,

    a에서 b로 순방향임을 저장하고,

    b에서 a로 역방향임을 저장해야 한다.

 

정답 코드

#include<bits/stdc++.h>
using namespace std;
#define MAX 100100
typedef long long ll;
struct node{int N,V,I;};
int n,cnt=0;
bool visited[MAX],ans[MAX];
int dp[MAX];
vector<node> tree[MAX];
void dfs1(int cur){
    if(visited[cur])
        return;
    visited[cur] = 1;
    for(auto next : tree[cur]){
        if(visited[next.N])
            continue;
        if(!next.V) cnt++;
        dfs1(next.N);
    }
}
void dfs2(int cur){
    if(visited[cur])
        return;
    visited[cur] = 1;
    for(auto next : tree[cur]){
        if(visited[next.N])
            continue;
        if(next.V){ // 순방향이면
            dp[next.N] = dp[cur]+1;
        }
        else{ // 역방향이면
            dp[next.N] = dp[cur]-1;
        }
        dfs2(next.N);
    }
}
void dfs3(int cur){
    if(visited[cur])
        return;
    visited[cur] = 1;
    for(auto next : tree[cur]){
        if(visited[next.N])
            continue;
        dfs3(next.N);
        if(next.V == 0)
            ans[next.I] = 1;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0; i<n-1; i++){
        int a,b; cin>>a>>b;
        // 1 : 순방향 / 0 : 역방향
        tree[a].push_back((node){b,1,i});
        tree[b].push_back((node){a,0,i});
    }
    dfs1(1);
    memset(visited,0,sizeof(visited));
    dp[1] = cnt; dfs2(1);
    int MIN=1e9,ans_node;
    for(int i=1; i<=n; i++){
        if(MIN > dp[i]){
            MIN = dp[i];
            ans_node = i;
        }
    }
    memset(visited,0,sizeof(visited));
    dfs3(ans_node);
    for(int i=0; i<n-1; i++)
        cout << ans[i];
    return 0;
}