[Network flow, MCMF] Graph modeling practices - Codeforce 편

[Network flow, MCMF] Graph modeling practices

  네트워크 플로우 및 MCMF에서는 그래프 모델링이 큰 비중을 차지합니다. 모델링을 하고나서 플로우 흘리는 개념은 고정되어 있으나, 그 문제가 그래프인지 또 그래프임을 알더라도 모델링을 하지 못하면 풀기 못하는 경우가 허다합니다.

  이 게시물은 그래프 모델링에 있어, 신기하거나 재밌게 느꼈던 문제 및 제가 어떻게 그래프 모델링 했는지 소개하고자 합니다. 물론! 다른 풀이가 있을 수 있으니 참고바래요 :)

  ※ 이분 그래프에 대한 내용은 포함되지 않았습니다. 호프 크로프트 또는 이분 매칭 문제를 찾으시는 분은 다른 게시물을 찾아보시길 바래요.

  ※ 소스코드는 일부러 첨부하지 않았습니다. 제 소스가 궁금하신 분들은 댓글 남겨주시면 쪽지나 메일로 보내드리겠습니다.

* Codeforce

1. Gourmet and Banquet (http://codeforces.com/contest/589/problem/F)

문제 목적은 명확하다. i번째 음식에는 [ai, bi) 시간 구간 동안 먹을 수 있으며 모든 음식을 k초간 동일하고 먹고자 할 때, 가장 큰 k를 찾는 것이다. 

1초에 하나의 음식만을 먹을 수 있으며, 1초 사이에 다른 음식을 바꿔서 먹을 순 없다. 0.5초는 A음식 먹고 0.5초는 B음식을 먹을 순 없다.

[풀이]

  시간을 노드로 보자. 그러면 각 음식에는 연속 구간 [ai, bi)에 해당하는 모든 시간 노드에 연결될 수가 있다. 1초에 하나의 음식을 먹을 수 있으므로 시간 노드에서 Supersink로는 용량이 1임을 직관적으로 알 수 있다. 또 음식에서 시간으로 가는 간선에 대한 용량은 1로 생각할 수 있다.

  이제 문제가 되는 부분은 Supersource에서 음식으로 가는 간선이다. 우리가 구하고자 하는 것은 모든 음식을 k초씩 먹고싶다 이다. 따라서 이 간선의 용량은 0부터 10000까지 답이 될 수 있다. 여기서 용량은 "먹은 시간"을 말하므로 이 용량을 x로 설정했을 때, 최대유량이 x*N가 되는 x의 최대가 k가 됨을 알 수 있다.

2. Array and Operations (http://codeforces.com/contest/498/problem/C)

상당히 재밌는 문제. 나는 이런 약수에 대한 그래프 문제가 좋더라..

  문제에서 원하는 것은 다음과 같다. i번째와 j번째가 i+j가 홀수라면 좋은 짝(pair)라고 정의해둔다. 좋은 짝끼리는 1보다 큰 임의의 정수에 대해 a[i]를 v로 나눌 수 있고, a[j]를 v로 나눌 수 있으면 a[i]와 a[j]를 v로 나누고 한 번 연산했다고 정의한다. 이 때, 주어진 배열 a에 대해 연산할 수 있는 최대 연산 수를 구하는 문제다.

[풀이]

  먼저 배열의 길이가 2일 때를 생각해보자. a[1]과 a[2]에 대해 연산 수를 최대로 한다는 것은 v로 나눌 수 있는 회수를 최대로 한다는 것이다. 그렇다면 탐욕법에 의해 v는 소인수임을 알 수 있다.

  배열의 길이가 2보다 클 때를 생각해보자. 그러면 i번째 수와 j번째 수 (단 i+j는 홀수)에 대해 소인수를 흘러보낼 수 있는 최대 수, 즉 최대 유량을 구하는 문제다.

  이제는 그래프를 그려야 한다. 하지만 소인수가 한두가진가? 아니, 가능한 소수의 범위는 [2, 10^9]이기 때문에 그 사이에 있는 소수를 구하면된다. 또한 알아야할 점은 소인수 간에는 최대 유량은 각각 "독립"적이다. 즉 v=2일 때 흘릴 수 있는 최대유량과 v=3일때의 최대유량이 독립적이라는 것이다. 이는 곧 그래프 형태가 다름을 뜻하며 범위 [2, 10^9]에 해당하는 소수마다 그래프를 구성해줘야 한다.

  각 Component는 index 노드들로 구성이 되는데, 플로우는 방향 그래프이기 때문에 i에서 j로(단 i+j는 홀수), j에서 i로 가는 간선을 각각 만들 수는 없다(중복 및 무한 루프로 빠지기 때문). 따라서 방향 그래프로 만들어야 한다. 조건을 보면 i+j는 홀수다. 홀수로 만들 수 있는 경우는 짝수 + 홀수 밖에 없다(이 관찰은 여러 문제에서 많이 쓰기 때문에 어느 정도 감만 쌓으면 볼 수 있게 된다). 따라서 Supersource->짝수->홀수->Supersink로 하든 홀수->짝수로 하든 정해주자.

  각 Component에서 S-i와 j-T관계에서 v로 나눌 수 있는 최대값으로 용량을 설정하여 연결하고, i-j에서는 용량을 INF로 설정한다(INF가 아니라 둘 중 작은 값으로 설정해도 되지만 큰 의미가 없다. 결국 양쪽 용량에 의해 설정되기 때문).

  그래프를 완성했으니 최대유량을 구해주시면 되겠다.

3. Ciel and Duel (http://codeforces.com/contest/321/problem/B)

으음.. 이 문제는 다이나믹으로 푸는 것이 훨씬 깔끔하고 접근법이 보다 간단하다. 이걸 유량으로 보려다보니 겁나 어려운 그래핑 및 간선 처리가 필요했다. 이 문제 같은 경우에는 그래프가 완성된 상태에서 답을 구할 수 있는 것이 아닌 그래프를 동적으로 변경하면서 유량을 구해야 했다는 것이 신기하다. 이 풀이는 순수 필자의 의견이니 이런식으로 풀 수 있을 것 같다고만 생각해주길 바란당.

  문제 목적은 간단하다. 현재 자신은 공격 카드밖에 없으며, 이 카드로 상대에게 공격할 수 있는데, 상대의 공격 카드에 공격하면 내 공격력 X가 상대 공격력 Y보다 크다면 상대는 X-Y만큼의 데미지를 받지만, 상대의 방어 카드에 공격하면 X가 상대 방어력 Y보다 크다면 상대는 0만큼 데미지를 받는다. 두 경우 양쪽 카드가 소멸된다. 이 때 상대가 받을 수 있는 데미지의 최대값을 구하는 것이다. 추가적으로 상대가 카드가 없고 자신이 카드가 남았을 경우 상대는 내 공격력 X를 그대로 받는다.

[풀이]

  마지막 조건 없이 생각해보자. 마지막 조건은 내가 카드가 남았을 때, 상대에게 공격을 못한다고 생각해보자는 것이다. 그러면 문제는 매우 플로우로 간단해진다. 내 카드 Xi에 대해 상대 카드(공격 및 방어) Yi보다 크다면 간선으로 연결하고 상대 카드가 공격이냐, 방어냐에 따라 Cost를 결정해주면 된다. 내 카드는 Supersource와, 상대 카드를 Supersink로 연결한 뒤, MCMF를 돌려버리면 매우 깔끔하게 그것도 직관적으로 답을 도출해낼 수 있음을 알 수 있다.

  하지만 마지막 조건을 추가하는 순간, 이 플로우 이후 사용하지 않은 카드를 그대로 보내는 것이 맞다는 것을 증명할 수 없다. 즉 문제를 플로우+그리디로 풀었기 때문에 최대유량 최소비용을 통해 답을 도출해내고자 MCMF를 쓴건데 거기에 그리디가 들어가버렸으니, 이러면 플로우로 풀었다고 볼 수 없기 때문이다.

  따라서 최대 유량을 내 카드 수로 맞춰야 한다. 상대 카드가 자신의 카드보다 많을 경우엔 내 카드 수로 유량이 맞춰지겠지만, 적을 경우엔 상대 카드 수로 맞춰진다. 설정한 Supersink는 데미지를 입는 대상이라고 하면, MCMF 이후 내 모든 카드를 Supersink에 코스트 X, 용량 1로 간선을 추가한 뒤 또 MCMF를 돌린다. 이렇게하면 상대 카드를 모두 소진한 것을 가정하고 남은 카드로 공격했을 때의 최소비용을 구할 수 있다.

4. Soldier and Traveling (http://codeforces.com/problemset/problem/546/E)

  N개의 도시에 M개의 도로로 연결되어 있고, 각 도시마다 군인이 있는데, i번째 도시에 있는 군인은 a[i]명이 있다. 여기서 군인들이 움직일 수 있는데, 그 도시에 머무르거나 현재 도시와 직접접으로 인접한 도시(도로를 하나만 건널 수 있음)로 이동할 수 있다. 이동 후에 i번째 도시에 머무르는 군인이 b[i]일 때, 이것이 가능한지의 여부와 어떻게 이동하면 되는지를 구하는 문제다.

[풀이]

  이 문제는 Div.2 E번 문제 치고는 그래프가 간단하다. 단 하나의 도로를 사용해야 하므로 도로를 통해 이동한 군인은 다른 곳으로 이동할 수 없게 해야 한다. 따라서 그래프 구성은 아래처럼 구성할 수 있다.

  Supersource와 초기 상태 a 배열에 대해 용량으로 볼 수 있고, Supersink와 이동 후의 상태 b 배열에 대해 용량으로 볼 수 있기 때문에, a배열 상태에서 b배열 상태로 될 수 있음의 여부는 최대 유량을 확인하면 된다. 당연 a의 총합과 b의 총합이 같아야 가능하다.

  따라서 도시 노드를 분할하여 하나는 이동 이전, 하나를 이동 이후로 둔 뒤 Max flow를 돌리면 된다.

5. Fox And Dinner(http://codeforces.com/problemset/problem/510/E)

  문제 조건은 이렇다. 여우들끼리 밥을 먹고자 한다. 테이블은 여러개 있다고 가정한다.

1. 테이블을 앉을 때, 둥그렇게 앉는다.

2. 각 테이블에서 인접한 두 여우 나이의 합은 소수이어야 한다.

3. 테이블을 할당할 때, 테이블 당 적어도 세 마리 이상의 여우가 있어야 한다.

[풀이]

  문제 설명에서 벌써 힌트를 줘버렸다. 할당. Assignment. 뭔가 이분 매칭의 냄새가 난다. 하지만 3번 조건에 의해 이분 매칭이 아니라는 점은 확연하게 알 수 있다.

  먼저 소수 부분은 에라스토테네스로 충분히 구할 수 있으므로 추가 설명하지 않겠다.

  그래프를 구성하기 위해서는 정점의 순서를 정할 필요가 있다. 소수는 홀수이고, 두 자연수 합이 소수가 되기 위해서는 하나는 홀수, 하나는 짝수여야만 가능하다. 따라서 순서를 홀->짝으로 하던지 짝->홀로 하던지로 분리할 수 있다. 그러면 마치 이분 매칭의 그래프처럼 나타나는 것을 볼 수 있다.

  다음을 구성하기 앞서 관찰을 먼저 해보자. 각 여우 정점은 반드시 하나만 사용해야 한다. 둥글게 앉기 때문에 인접한 여우는 반드시 둘이다. 그 이상도 그 이하도 아니다. 2번 조건을 보면 최소 3마리 이상의 여우가 하나의 테이블에 있어야 한다는데, 3마리로 테이블을 앉힐 순 없다. 따라서 이 조건은 낚시이고 4마리 이상의 여우가 앉아야 할당이 가능함을 알 수 있다. 쨌든 하나의 여우에는 두 인접한 여우가 있으므로, 두 여우와 매칭을 해야한다는 결론이 나온다. 따라서 홀수 정점과 짝수 정점이 Supersource 또는 Supersink와 연결되는 간선의 용량은 딱 2로 정하면 된다.

  그래프가 구성됐으니, 플로우를 돌린 후의 결과는 Supersink와 연결된 정점의 개수를 Vc라고 할 때, flow = Vc * 2이어야 한다. 이외엔 Impossible을 출력해주시면 되겠다.

  flow = Vc*2라면 이를 추적하는 코드는 그다지 어렵지 않으므로, 단순 사이클을 찾는 것(테이블을 둥글게 앉는것)으로 충분히 구현 가능하다.

6. Binary Tree on Plane (http://codeforces.com/contest/277/problem/E) [HARD]

  주어진 좌표들을 이진 트리로 만들어야 한다. 단 조건은 부모 노드가 자식 노드보다 y의 좌표값이 커야 가능하다.

  Flow 문제라는 것을 알고 들어가기 때문에 공략법이 어느정도 보이나, 당시 콘테스트 때는 어떻게 풀어야할 지 고민 많이 했을 것 같다.

[풀이]

  만약 이진 트리가 아니라면 스패닝 트리로 구성할 수 있으므로, 탐욕법(프림 또는 크루스칼)을 이용하여 최소 스패닝 트리로 답을 도출해낼 수 있다. 하지만 자식의 수가 최대 두 개이므로 단순 스패닝 트리로 구성하여 이진 트리를 만들 순 없다.

  따라서 먼저 관찰해야 할 점은 yi < yj < yk (1<= 서로 다른 i,j,k <= n)일 때, yi가 반드시 yj의 자식이라고, 또는 yj가 yk의 자식이라고 할 수 없다. 즉 y 좌표값이 인접해 있다고 해서 반드시 두 노드가 연결되어야 할 필요가 없다는 것이다. 따라서 어떤 정점 yi값보다 작은 y를 갖는 좌표에 대해서 이진 트리를 구성할 수 있기 때문에 "계산"되어야 한다.

  이진 트리기 때문에 좌표 당 최대 두 개의 자식을 가질 수 있다. 이는 직관적으로 supersource에서 해당 좌표의 용량으로 볼 수 있다. 그렇다면 supersink는 어떻게 잡아야 할까.

  부모와 자식을 "억지로" 간선을 통해 연결시키도록 해야 한다. [부모와 자식을 연결할 간선을 0보다 매력적일 만큼 음수로 만들어서 MCMF로 하는 방법? 이 방법은 안된다. 자칫 하나의 간선이 아니라 여러 간선을 계속 타며 갈 수 있기 때문이다. 이 결과는 좌표 노드를 유량 1로 보는 것이 아니게 된다.]

  따라서 좌표 정점을 분리 시켜버린다. 하나는 supersource와 또 다른 하나는 supersink와 연결한다. 이젠 yj < yi일 때, i번째 정점을 j번째 정점과 연결시키기 위해선 i의 분할 정점 첫 번째(supersource와 연결된)와 j의 분할 정점 두 번째(supersink와 연결된)과 해당 거리만큼 cost를 할당한다. 이렇게 그래프를 구성하고 MCMF를 구성하고, 유량이 n-1이면 이진 트리를 구성할 수 있음을 뜻하고 아닌 경우는 답이 없는 경우다.