ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 12784 인하니카 공화국
    알고리즘 문제/DFS and Simillar 2018. 5. 29. 17:16

    백준 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


    '알고리즘 문제 > DFS and Simillar' 카테고리의 다른 글

    백준 12784 인하니카 공화국  (0) 2018.05.29
    백준 2447 별찍기10  (0) 2018.03.06
    884C Bertown Subway  (0) 2017.11.05
    BoJ 1717 : 집합의 표현  (0) 2017.10.29

    댓글 0

Designed by Tistory.