백준 12784 인하니카 공화국

백준 12784

인하니카 공화국 문제는 흥미로운 문제였다. 

인하니카는 섬으로 이루어진 나라인데, 각 섬은 다리들이 연결하고 있다. (그래프 ,,, ?)

다리는 모든 섬을 연결할 수 있는 최소한의 개수로 사용되고 있다. (트리 .. !)

다리가 한 개인 마을에 살인마가 존재하기 때문에 내가 사는 곳(1번 노드) 과 끊어야한다.

이때 각 각의 다리를 끊는 비용은 주어질 때, 살인마가 존재 할 가능성이 있는 모든 마을에 대해 다리를 끊을 때 최소비용 을 구하라. 라는 문제이다.

이 문제는 난해할 수 있는데, 생각대로 깊이 우선탐색을 구현하면 쉽게 해결 할 수 있다.

그러나 나는, 이 문제를 통해 좀 더 확장할 수 있는 재귀탐색 기법을 보여주고 싶었는데

이 문제는 조금만 뉘앙스를 바꾸면, 

트리에서 루트노드에서부터 모든 리프노드까지의 최대유량문제가 된다.

왜냐하면 

"루트노드에서 모든 리프노드까지의 경로를 제거하는 최소 비용은 ... "

간선비용을 간선 용량으로 바꾸면

"루트노드라는 입구로 물을 부어넣어서 모든 리프노드라는 출구로 배출될 수 있는 최대유량 ... " 

과 같아진다.

"나 이거 비슷한거 들은거있어... 설마 Max-flow Min-cut Theorem...?!!!...."

네 맞습니다 

root 노드를 s라 하고

leaf node 에 굉장히 큰 용량의 간선 하나씩을 추가해서 한 노드로 향하게 하고 그것을 t라고하자.

우리는 s->t를 갖게된다. 그리고 완벽하게 max-flow 문제가 되는것이다.

사실 최대유량의 문제는 보통 임의의 그래프에서 해결하는 문제이다. 

그렇지만 트리에서의 최대유량이면 어떤가,,,,,! 위의 예시처럼 leaf node에 각 간선을 추가해서 

한 노드로 향하게 하면 완벽히 s->t with dag(directed acyclic graph)이 되는것이다. 

따라서 구현에서의 둘의 공통점은 있다.

우선 임의의 지점에서 dfs 탐색을 할 것인데, 시작점은 루트노드가 좋다.

따라서 메인에서는 다음과 같이 호출될 수 있다.  -> dfs(1)

임의의 지점에 들어간다고하자.

void dfs ( int now )

{
chk[now] =1;

for (int i=0; i<e[now].size(); i++)

{
  if ( chk[e[now][i]] == 0 ) dfs(e[now][i]]);

}

}

이로써 모든 노드까지 탐색은 가능하다.

다만 한 노드로 재귀 함수가 들어갔을 때 어떤 행위를 해야하냐는 의문점이 있을 것이다.

그게 바로 문제가 요구하는 것인데, 

한 노드로 재귀 함수가 들어갔을 땐 다음 두가지를 비교하여 문제를 해결 할 수 있다.

1 자기 자신과 자신의 자식들을 연결한 모든 간선의 비용 합

2 자기 자신과 자신의 부모를 연결한 간선의 비용

우선 다음을 확인하라.

다음과 같은 문제는 cost(a) + cost(b) + cost(c) + cost(d) 가 정답이 되어야한다.

만약 다음과 같은 경우를 생각해보자.

이때 cost(a) 는 cost(aa) + cost(ab) + cost(ac) 와 비교하여 더 적은 비용으로 교체될 수 있다.

우리는 cost (a) 와 cost(aa) + cost(ab) + cost(ac) 를 비교하는 것은 깊이 우선탐색으로 구현할 때 그 사이의 노드를 탐색 중일 때 비교하는 것이 효율적임을 알 수 있다. 

왜냐하면 그런 위치에 있는 노드가 부모 및 자식 간선을 가지기 때문이고 구현할 때 용이하기 때문이다.

따라서 우리는 기존 dfs 함수를 조금 변형할 수 있다. 해당 노드로 내려갈 때, 내가 어떤 간선용량을 사용했는가를 기록해두자.

dfs(int now, int cost)

{

  int ret = cost;

  for (int i=0; i<e[now].size(); i++) 

      if( chk[e[now][i]] == 0)  dfs(e[now][i].v , e[now][i].cost);

  return ret;

}

그 뒤 우리는 비교 구문만 추가해서 해결하면 된다.

dfs(int now , int cost )

{

  int ret = cost;

  int child =0;

  for (int i=0; i<e[now].size(); i++)

     if( chk[e[now][i]] == 0 ) child+= dfs(e[now][i].v, e[now][i].cost)

   return min(ret, child);

}

그리고 마지막 노드에 대한 예외처리만해주면 끝이다. 이 점은 맨 아래에 소스보기를 통해 확인하기를 바란다.

문제의 유형이 최대유량과 유사하므로 dfs에서도 유사한 모습이있다. 여기서 int cost 라는 변수인 부분이 비슷한것이다. 

이 부분은, 내가 지나온 간선의 weight(또는 capacity라고도 불릴 수 있음)를 전달받는 데, dfs를 이용한 최대유량 문제해결에서도 볼 수 있는 부분이다.

소스보기 

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/12784.cc