[Network flow, MCMF] Graph modeling practices - 백준 편
coloredrabbit
2018. 10. 18. 17:22
[Network flow, MCMF] Graph modeling practices
네트워크 플로우 및 MCMF에서는 그래프 모델링이 큰 비중을 차지합니다. 모델링을 하고나서 플로우 흘리는 개념은 고정되어 있으나, 그 문제가 그래프인지 또 그래프임을 알더라도 모델링을 하지 못하면 풀기 못하는 경우가 허다합니다.
이 게시물은 그래프 모델링에 있어, 신기하거나 재밌게 느꼈던 문제 및 제가 어떻게 그래프 모델링 했는지 소개하고자 합니다. 물론! 다른 풀이가 있을 수 있으니 참고바래요 :)
※ 소스코드는 일부러 첨부하지 않았습니다. 제 소스가 궁금하신 분들은 댓글 남겨주시면 쪽지나 메일로 보내드리겠습니다.
* 백준
백준 사이트는 보통 문제가 2차 출처입니다. 원본 출처는 다른 곳이 있을 수 있으니 참고해주세요.
1. 마피아 (https://www.acmicpc.net/problem/1210)
시작 도시와 도착 도시가 주어졌을 때, 못 가도록 도시를 점령하여 지나가지 못하게 할 때, 최소 비용으로 마피아를 막아야 한다는 컨셉.
[풀이]
문제 자체는 학교 가지마! 와 매우 유사하다. 그 말은 즉, 최소 컷을 생각할 수 있어야 한다. 하지만 비용의 개념이 들어가서 다소 헷갈릴 수 있다. 하지만 이는 분명 MCMF가 아닌 Min cut 문제다. 특정 도시 Di에 대해 Ci의 비용이 든다고 한다면, 이를 용량으로 둔다. 각 도시간의 연결은 용량을 무한대로 두고, 해당 비용을 분할 정점 사이의 용량으로 둠으로써 도시에서 도시로 이동하기 위해서는 반드시 분할 정점 사이의 간선을 지나야 하며, 해당 비용 만큼 유량을 흘릴 수 있는 구조가 된다. 이때 최대 유량을 모두 구한 상태를 생각해보자. 어떤 도시의 분할 정점 간선은 용량=유량 일 수도 있고 용량 > 유량 일 수도 있다.
1. 용량=유량
용량과 유량이 같다면 Min cut의 일부분으로 볼 수 있으며, 해당 도시를 점령해야 한다.
2. 용량>유량
해당 도시보다 다른 도시를 점령하는 것이 다 낮은 비용(유량)으로 마피아를 막을 수 있다.
하지만 이런 포화 상태에서 1.의 조건만으로는 답을 도출해 낼 수 없다. 왜냐하면 최소 컷의 후보는 하나가 아니기 때문이다.
[그림 1]
따라서 다시금 시작 도시에서 BFS를 돌려서, 막힌 간선을 만날 때 까지 방문하며(residual capacity = 0) 라벨링을 하고, 더 이상 나아갈 수 없는 정점을 추출해내서 이를 답으로 출력하면 되겠다.
다소 관찰이 필요한 문제다. 두 시스템의 공통점을 생각해보자. 링 구조는 사이클을 이루고, 선 구조는 사이클을 이루지 않는다. 하지만 둘 다 하나의 노드에 대해서 진입 간선 수가 1이고 진출 간선 수가 1이다. 이말은 즉, 특정 간선을 고르기 위해서는 시작 노드의 진출 간선 수가 0이어야 하고, 도착 노드의 진입 간선 수가 0이어야 한다는 것이다. 따라서 이를 통해 이분 그래프를 구성할 수 있으며 답은 곧 이분 매칭으로 답을 도출해낼 수 있음을 알 수 있다.
[그림 2]
3. 범죄 파티(https://www.acmicpc.net/problem/13166)
범죄자마다 두 명의 친구가 있으며, 각각 꼬드기기 위해서 필요한 비용이 있을 때, 모든 범죄자가 변호인을 얻으려면 K비용이 드는 파티를 열고자 할 때, K의 최소값을 구하라.
[풀이]
단순히 K비용으로 모든 범죄자의 친구를 꼬드길 수 있는 점에서 간선 정보는 간단해진다는 걸 알 수 있다. 가령 친구를 변호인으로 두기 위한 비용이 Ci 일때 이 값이 K보다 작거나 같으면 변호인으로 둘 수 있으며, 아니면 변호인으로 둘 수 없다. 또 변호인을 여러명으로 둘 수 없으므로 이분 매칭임을 알 수 있다.
최소 K를 찾기 위해서는 이분 탐색으로 진행할 수 있다.
[그림 3]
4. 졸업(https://www.acmicpc.net/problem/1575)
이미 들은 수업과 졸업 조건이 여러 개가 있을 때, 졸업하기 위해서 들어야 하는 수업들을 구한다. 단 경우의 수가 많으므로 수업 수를 최소로, 수가 같다면 사전순으로 앞서는 것을 출력한다.
[풀이]
졸업하기 위한 조건을 생각해보자. 졸업 조건마다 "들어야 하는" 수업의 수(Ci)가 정해져 있다. 그 이후 몇 개의 수업 안에서 Ci개를 선택해서 조건을 만족시킬 수 있어야 한다는 것인데, 어떤 방식으로 조건을 만족시키건 무조건 졸업 조건을 만족시키기 위한 Ci는 고정이다. 모든 졸업 조건의 합 matched는 다음과 같은 수식을 만족한다. [수식 1]
따라서 이 문제를 유량 문제로 볼 수 있으며 최대로 흘릴 수 있는 유량이 곧 matched가 되야 졸업할 수 있음을 알 수 있다.
이제 그래프 구조를 확인하자. 수업은 반드시 노드로 표현해야 한다. 그렇다면 졸업 조건은 어떻게 표현해야 할까. 크게 보면 졸업 조건을 그 조건에 해당하는 수업과 모두 연결지을 수 있다. 하지만 이는 수업의 수(Ci)를 표현할 순 없다. 따라서 이 구조에서 졸업 조건을 Ci개 만큼 노드로 분할한다. 분할된 노드에 대해 해당하는 수업을 모두 이어 붙여주면 유량(매칭)은 만족하는 조건의 수로 볼 수 있게 된다. 또한 이러한 양립적인 구조는 이분 그래프를 구성하므로 이분 매칭으로 풀 수 있게 된다.
[그림 4]
5. 숫자판 만들기(https://www.acmicpc.net/problem/2365)
NxN 2차원 배열에서 가로의 합과 세로의 합이 주어졌을 때, NxN을 채우려고 한다. 이 때 채워질 칸의 수를 되도록 최소로 할 때 가능한 경우를 출력한다.
[풀이]
여기서의 자원은 어떤 것일까? 당연히 쓰여지는 수를 자원으로 볼 수 있다. 따라서 행의 합과 열의 합에 대해서도 자원으로 표현할 수 있으며 전체적으로 자원을 유량으로 표현할 수 있다.
행과 열을 각각 N개의 노드로 표현하고, 각각을 supersource, supersink와 연결한다. 가령 supersource와 행 노드를, 열 노드와 supersink와 연결시키는 것이다(반대로 해도 상관없음). 그 사이의 용량은 해당 행 또는 열의 합(자원, 즉 유량)이 들어가게 된다. 이제 내부적으로 처리를 해야하는데, 여기까지 눈치를 챘다면, 간선에 흐르는 유량 자체가 수를 뜻하기 때문에 N*N개의 노드의 간선을 조작하며 답을 도출해야 한다. 이 문제는 사용하는 수의 최대값을 가장 작게하고 싶으므로 사용하는 수, 즉 간선 용량에 대해 이분 탐색을 진행한다. 그렇다면 이 간선은 어디서 사용되어야 할까? 해당 칸에 수를 채우고 싶기 때문에 칸 안에 간선이 있어야 한다. 따라서 행 또는 열 집합에 대해 칸 노드로 가는 용량을 탐색하는 것으로 진행한다. 둘 중하나만 설정해서 둘 중 하나만 찾아가도록 설정한다. 나머지 하나는 INFINITE로 설정하여 최대용량으로 설정한다(둘다 설정해도 상관 없긴함).
[그림 5]
6. 수영장 만들기(https://www.acmicpc.net/problem/3656)
상당히 재밌는 문제. 무려 비용이 세 개나 들어가 있다. 보통 2차원에 대해서 두 개의 비용으로 관계를 묻지만 이 문제의 경우엔 하나가 더 추가됐다.
[풀이]
MCMF로 생각하기 쉬우니 먼저 MCMF로 접근했다고 해보자. 그러면 정점을 분할하여 잔디일 때와 구멍일 때의 간선을 나눠서 비용 d와 f에 대해서 처리해줄 수 있다. 하지만 잔디와 구멍에 대해서 벽을 치는 비용 b에 대해서 처리를 해주기 위해서는 간선을 생성해서 처리를 해줘야 하는데 이러면 하나의 cell에 대해 유량이 2 이상으로 구성할 수 밖에 없다. 결국엔 그래프가 뭉그러지며 머리속은 복잡해지고 문제를 풀기 싫어진다. 는 내 경험이고. 유량이 2 이상으로 구성되면 supersource와 supersink에 대한 용량, 간선 용량에 대해 처리하기가 어렵다.
그럼 다음 수로 최소 비용을 계산하기 위해 최소컷을 생각할 수 있다.
2차원 배열을 순회하며 현재가 잔디라면 supersource와 용량이 d로 간선을 연결하고, 구멍이라면 supersink와 용량 f로 간선을 연결한다. 각 cell에 대해 4인접 이웃을 검사하고 서로 용량 b로 간선을 연결해준다. 그러면 비용 f,b,d에 대해 그대로 둘 것인지 아니면 잔디를 구멍으로 또는 구멍을 잔디로 바꿀 것인지를 알 수 있다.
[ 그림 ]
※ 테두리에 대해서 반드시 잔디를 둬야한다는 점에서 휴리스틱하게 소스를 변경해야 합니다. 이는 여러분이 직접 생각해보는 것도 좋습니다.
7. 리스크(https://www.acmicpc.net/problem/3666) - 대회에 자주 사용 됨
내가 점령하고 있는 영역 중 적국과 인접한 영역에 얼마나 군대를 최대한 배치할 수 있는지에 대한 문제다. 여기서 내가 사용한 그래프 모델은 대회에서 자주 사용되므로 꼭 기억하고 넘어가자. 안 중요한 모델이 있겠냐만은.. 그래도 이 모델의 경우 쉽게 접근할 수 있다.
[풀이]
먼저 가장 취약한 영역이 어디인지 정해보자. 예를 쉽게하기 위해 영역이 총 4개, A와 B는 내가 가진 영역이고 C와 D는 적이 가진 영역이라 하자. 군대가 A에는 10이, B에는 4가 있으며 A-B, A-C, B-D 간선이 있다고 하자. 그러면 여기서 가장 취약한 영역은 어디일까? 과연 B만이 가장 취약한 영역일까?
B만 가장 취약한 영역이라면 A에는 1이, B에는 13이 주둔할 수 있다. 하지만 이런 배치는 결과적으로 적과 인접한 영역 중 가장 취약한 영역은 A로 변경되며 이는 문제에서 요구하는 결과와 다르게 되어 버린다.
- 정의 : 가장 취약한 영역은 내가 가지고 있는 영역 중 적국과 인접한 영역, 모두이다.
이제 문제는 가장 취약한 영역에 대해서 어떻게 "적절하게 분배하여 군대 수를 최대(k)로" 하는 것으로 변형할 수 있다. 이는 곧 모든 가장 취약한 영역은 "적어도" k의 군대가 주둔해야 함을 의미한다.
모든 영역은 인접한 영역으로 밖에 이동 할 수 없으므로 모든 영역에 대해 supersource와 이을 정점(이하 진입 노드라고 표현)과 supersink와 이을 정점(이후 진출 노드라 표현)으로 분할하여 인접한 영역에 대해서만 진입 노드에서 인접 영역의 진출 노드로 간선을 이어 준다. 이 모델링은 자주 사용되므로 기억하면 좋을 것 같다.
[ 그림 ]
이제 내가 가지고 있는 영역에는 적어도 군대 1이 주둔해 있어야 하므로 supersouce에서 진입 노드로의 용량은 ai로 설정, 진출 노드에서 supersink로의 용량을 1로 설정하면 되고, 가장 취약한 영역 모두에 대해 supersink로의 용량을 k로 둔다. k를 추적하는 일은 이분탐색으로 진행할 수 있고, 전체 flow가 (내가 가진 영역 개수) - (가장 취약한 영역의 개수) + k * (가장 취약한 영역의 개수) = (내가 가진 영역의 개수) + (k - 1) * (가장 취약한 영역의 개수) 를 만족하면 k를 답 후보로 둘 수 있다. 여기서 k의 최대값을 찾아서 출력해주시면 되겠다.
※ 같은 모델을 이용한 문제
- Soldier and Traveling (http://codeforces.com/problemset/problem/546/E)
8. It Can Be Arranged(https://www.acmicpc.net/problem/9590)
상당히 재밌는 문제.
BOJ 7064 - Air Raid 문제를 먼저 푸는 것을 적극 권장합니다.
[풀이]
문제를 다시 보자. 구하고자 하는 것은 방의 최소 값이다. 이런 관점에서 나는 "방의 개수"를 용량으로 봤다. 학생을 용량, 시간에 대해 노드를 분할하는 방법도 있을지 모르겠지만 최대한 간단한 방법으로 접근해봤다. 방의 최소값을 구하기 위해서 재활용 가능한 방의 수를 최대로 하는 것이다.
1. 먼저 시간에 상관없이 각 강의마다 방을 모두 빌린다고 생각해보자. 그러면 각 강의는 Si의 학생이 있으므로 방 하나의 크기 M에 대해서 wi를 O(1)만에 구할 수 있다. 이는 곧 supersource로부터 각 강의로 나가는 간선의 용량으로 볼 수 있다.
[정의] wi = 각 강의마다 필요한 최소 방의 수
2. 강의i가 끝나는 시간 Bi + clean_ij에 맞춰서 방을 재활용할 수 있다. 즉 아래 수식을 만족해야 방을 재활용할 가능성이 있다.
Bi + clean_ij < Aj
위를 만족한다면 강의 i가 쓴 방을 강의 j가 이어 받을 수 있다.
여기서 몇 개의 방을 이어 받을 수 있을까? wi로 설정할 수 있다. 어차피 supersouce로부터 wi가 설정되어 있기 때문에 그냥 무한한 값(INF)로 줘도 상관없다.
3. 1.에서는 supersource만 처리했다. 그렇다면 supersink는 어떻게 처리해야할까.
강의i에 대해 필요한 방의 수는 wi, 마찬가지로 재활용할 수 있는 방의 수도 wi이다.
4.[인계] 1-3까지 해결하다보면 당연히 방의 인계에 대해 처리가 필요하다. 가령 강의 A,B,C에 대해 A 끝나고 B, B가 끝나고 C 순으로 강의가 진행된다고 해보자. 그러면 A의 방이 B와 C 모두에서 재활용되는 것이 좋다. 이는 1-3에서 한 결과로 충분히 넘어갈 수 있다.
문제는 A 끝나고 B, C가 가능하고 B와 C가 서로 이어서 진행할 수 없는 강의라고 해보자. 그러면 A의 재활용 가능한 방은 어디로 가야할까 ? B와 C 중 먼저 시작하는 강의에 넘겨줘야할까? 아니다. 강의 B에 대해 재활용 가능한 방을 모두 할당된 상태라면 이를 그대로 흘려야할 필요가 있다. 따라서 이 인계를 극복하기 위해 2.에서 추가적인 과정이 필요하다.
먼저 각 강의를 두개의 정점으로 정점 분할을 해야한다. 하나(SCi)는 supersource로 하나(TCi)는 supersink로 간다.
Bi + clean_ij < Aj라면 TCi에서 TCj로 방의 개수(용량)을 무한(INF)로 둔다. 반드시 무한으로 둬야하는 이유는 여기로 흐르는 방에 대한 "인계"가 어느 강의로부터 왔는지 모르기 때문이다.
[그림]
여기로 최대로 흐른 플로우는 "재활용 가능한 방"의 수임을 재차 강조합니다.
9. 나는 9999번 문제를 풀 수 있다(https://www.acmicpc.net/problem/9169)
[풀이]
구하려 하는 것이 정확히 뭔지 다시 봐보자. 자신의 생각을 바꿔야 하는 사람 그리고 친구인데 다른 투표 결과인 사람의 합을 최소로 해야한다. 마치 따로 구하는 것처럼 서술되어 있지만 중복은 포함하지 않는다. 즉, A라는 사람이 자신의 생각을 바꿔야 하며 자신의 친구 B와 생각이 다르다면 두 번 중복하여 셈을 하지 않는다.
먼저 관찰해야 할 점은 각 친구 간의 관계가 근시적으로 연결되어 있다는 점이다. A와 B가 친구고, B와 C가 친구라고 해서 A와 C가 친구라는 보장이 없다. 마찬가지로 문제에서 요구된 내용에 A와 C가 끼어들어갈 자리가 없다. 즉, A만 놓고 봤을 때, A와 친구인 노드들만 사용하여 답을 도출해내야 한다.
A와 친구인 사람들을 두 집단으로 나눌 수 있다. 9999번을 풀 수 있다라고 생각하는 집단(G1), 풀 수 없다 집단(G2)로 나눠보자.
[1] A가 G1 집단과 다른 생각을 가지고 있다고 가정해보자. 즉 A는 9999번 문제를 풀 수 없다라고 생각한다. 현재 G1과 A가 친구인데 의견이 다르므로 G1만큼 증가한다.
[2] 반대로 A가 자신의 생각과 다르게 했다고 가정해보자. 즉 A는 9999번 문제를 풀 수 있다고 생각한다. 그러면 G2와 A가 친구인데 의견이 다르므로 G2만큼 증가한다. 여기서 A의 생각을 바꿨으므로 +1.
위와 같이 서로 의견이 다른 친구에 대해서 어느 경우에 문제에서 요구하는 작은 값을 도출해낼 것인지가 문제다.
[모델링 1] G1과 G2는 A에 의해 간접적으로 연결되어 있다. 즉 G1-A-G2의 연결성을 보장해야함을 알 수 있다.
[모델링 2] 모든 사람은 단 한 번만 셈이 되어야 하므로 사람 노드에 대한 최대 유량은 1이다.
[모델링 3] A와 B가 같은 생각을 하고 있는 친구라면 용량 1의 A->B, B->A을 생성해준다.
[모델링 4] A와 B가 다른 생각을 하고 있는 친구라면 supersource에서 나가는 간선을 "풀 수 있다" 집단이라면 풀수 있다라고 생각하는 친구에서 풀 수 없다고 생각하는 친구로 용량 1로 연결해준다.
[모델링 4]에서 친구 관계를 근시적으로 보게끔 함으로써 경우의 수를 최소컷에 기반하여 자연스럽게 어떻게 투표를 해야 문제에서 요구하는 최소값이 나올 수 있는지 알 수 있다.
[그림]
10. 떡국(https://www.acmicpc.net/problem/1127)
11. Decoding Ancient Message(https://www.acmicpc.net/problem/10625)
2차원 문자열 배열에서 문자를 (i, j)에서 뽑아낼 때, 이 다음 문자열을 뽑을 때는 i행과 j열에서 후보를 제외할 때, 뽑을 수 있는 문자열에 대해 사전순으로 가장 앞서는 것을 출력하는 문제다. 사전순으로 답을 내는 것이 여간 까다로운 문제가 아니다.
[풀이]
행과 열에서 하나씩만 뽑는 것은 이분 그래프로 나타낼 수 있으며, 최대 매칭 n이 되도록 문자열을 선택하는 문제로 볼 수 있다. (이분 그래프에 대한 설명이 너무 축약되어 있는가? 이 문제 말고 다른 문제를 먼저 풀길 진심으로 권장합니다.. 무시해서가 아니라 여러 개념이 섞인 이 문제를 푸는 것보다 보다 쉬운 문제를 푸는 것이 분명 효율적일 겁니다.)
단순히 생각하면 모든 우선순위가 알파벳 순이므로, 그 ASCII 코드 상의 코스트를 그대로 적용하여 MCMF를 돌리면 되지 않을까라고 생각할 수 있다. 하지만 함정이 있는데 가령 AAC와 ABB를 비교해볼 때, cost는 같으나 사전적으로는 AAC가 더 앞서므로 답으로 출력해야 하는 것은 AAC가 된다. 따라서 전체 cost가 같더라도 사전적으로 출력하기 위해서는 내부적으로 cost를 조정해야할 필요가 있다는 것이다.
(방법1) A-Z,a-z 순으로 상위로 올라갈 수 있도록 매칭을 조정한다. DFS 등으로 조정.
(방법2) 가중치를 우선순위로 둘 수 있도록 한다. 즉 cost를 자체를 우선순위로 보는 것이다(단순한 정수 합이 아님).
필자는 방법2가 더 간단해서 설명도 방법2로 설명하겠다.
말했듯, cost를 우선순위로 두어야 하기 때문에 기존 integer로 우선순위를 둘 수 없다. cost 각각 독립적으로 우선순위를 볼 수 있도록 강제적으로 해야한다. 마땅한 기본 자료형이 없기 때문에 직접 클래스나 구조체를 선언한다.
1. 크기 52의 정수 배열을 만든다.
2. 인덱스 번호가 0에 가까울 수록 우선순위가 높다고 설정한다.
3. 2.에 따라 52개 인덱스를 순회하며 우선순위가 높은 것을 코스트가 적다고 동치 관계를 형성한다.
이렇게 하면 단순 MCMF로 AC를 받을 수 있다. 이렇게 멀리 돌아가는 이유는 다시 말하지만 최소 비용 최대 흐름 중에서도 사전순으로 답을 도출해내야 하기 때문이다.
