티스토리 뷰
백준 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' 카테고리의 다른 글
백준 2447 별찍기10 (0) | 2018.03.06 |
---|---|
884C Bertown Subway (0) | 2017.11.05 |
BoJ 1717 : 집합의 표현 (0) | 2017.10.29 |
- Total
- Today
- Yesterday
- paul wilton
- 아레나
- 아레나시뮬레이션
- Discrete Mathematics
- 데이터 중심 애플리케이션 설계
- 시뮬레이션
- 이산 수학
- Arena
- arena simulation
- Simulation
- 자바스크립트
- flutter
- 명제논리
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- 그라파나
- Trie
- 항해99
- rosen
- Propositional and Predicate Logic
- 최단경로 알고리즘
- 백준
- beginning javascript
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- grafana cloud
- 로젠
- 이산수학
- javascript
- 자바스크립트 예제
- 대규모 시스템 설계 기초
- 아레나 시뮬레이션
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |