'ACM'에 해당되는 글 1건


예전에는 손도 못대던 문제가 그래프 관련 문제였다. 하지만, 의외로 많은 문제들을 그래프로 풀 수 있고 재미있는 문제들도 많다. 그래서 요새는 어떤 문제가 주어지면 혹시나
그래프로
그래프로 풀 수 있는게 아닌가부터 생각한다. 이번 문제는 문제만 읽어봐도 Maximum flow 문제라는 것을 알고리즘을 공부해본 사람은 누구나 알 수 있는 문제이다. 

학부 알고리즘 수준에서 NPC를 제외하면 제일 까다로운 부분이 아닐까 생각된다. 기초적인 부분을 제외하고 이론적으로 따지고 들면 따라가기도 꽤 어렵다. 어쨌든, 이 문제는 기본적인 Max flow 알고리즘을 따라가면서 풀면 쉽게(?) 풀린다. 가장 쉬운 Ford-Fulkerson 방식이다.

간략히 알고리즘을 살펴보자.
출발 노드(s)에서 끝 노드(t)까지 flow를 보낼 수 있는 path p를 찾아서 그 p를 이루는 edge들의 residual capacity (해당 edge로 더 보낼 수 있는 flow의 최대 크기)중에서 가장 작은 c_min를 먼저 구한다. BFS 혹은 DFS를 사용하여 해당 p가 존재하는지를 알 수 있다. p의 각 edge의 flow를 c_min만큼 증가(augment)시켜준다. 이러한 작업을 계속 하다보면 더 이상 s에서 t로 flow를 보낼 수 있는 길이 없게 되는데, 그 때 s에서 나가는 flow들의 합, 혹은 t로 들어가는 flow들의 합을 구하면 그게 Max flow가 된다.

처음에 당당히 WA(Wrong answer)를 받아서 왜 그런가 생각을 해봤다. 
  1. 먼저, 마침표(.)를 안 찍은 것을 발견했다. 또 다시 WA. 
  2. 이번에는 뭔가 구현상에 문제가 있는 것이 아닌가 생각을 했다. 교과서(CLRS)에는 anti-parallel edge만 존재한다고 가정한다. 따라서, 두 노드 사이에 edge가 어느 방향으로 있는지가 꽤 중요하다. augment하려는 edge가 존재하면 c_min만큼 flow를 증가시키지만, 해당 edge가 존재하지 않으면 반대 방향으로 flow를 증가, 즉, 원래 방향으로는 flow를 감소시켜야 한다. 하지만, 이 문제에서는 항상 bi-directional한 edge가 존재하므로 이 부분을 고려하지 않아도 된다고 생각했다. 그래서 다른 사람이 짠 소스를 살펴봤더니 a->b가 c_min만큼 증가되면, b->a는 c_min만큼 감소시켰다. 나도 그렇게 바꾸고 다시 제출했다. 그런데 역시 WA. 
  3. 이번에는 문제를 다시 읽어봤다. 각 test case마다 newline이 있어야 한단다. 추가했더니 AC(accepted)
  4. 다시 2번에서 고쳤던 부분을 원래대로 돌렸다. 역시 AC. 문제는 1, 3번이었다. 2번을 적용하도 않아도 되는 것이 맞는지, 아니면 우연히 맞은 것인지는 좀 더 생각해 봐야 한다.

댓글을 달아 주세요