[백준 11376번] 열혈강호2

www.acmicpc.net/problem/11376

11376번: 열혈강호 2

 

열혈강호1의 풀이를 두번씩 반복해주면 된다.

 

허무할 수도 있는 문제지만 정답을 보지 않고 이를 유추하기는 꽤 어려운듯하다.(적어도 나한테는...)

재귀함수 정의 자체를 수정해서 문제를 해결하려해서 문제가 상당히 복잡해졌었다. 

 

결국 해답을 보고 허무하기도 했지만, 이를 발견하지 못했던 것 역시 진정으로 이분 매칭 알고리즘을 이해하지 못했기 때문이었다는걸 느꼈다.

 

 

이번 문제는 시간 여유가 있어 이분 매칭, 포드-풀커슨 알고리즘을 각각 사용해 풀어봤다.

 

이분 매칭 버전

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
자바쟁이 - https://javachoi.tistory.com/

백준 11376번 - 열혈강호2
https://www.acmicpc.net/problem/11376

이분 매칭 version
 */
public class Main {
	static int N,M;
	static int[][] edge; //간선 : [직원][작업]
	static int[] matched;
	static boolean[] visited;
	public static void main(String[] args) throws Exception {
//		BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
		edge = new int[N][M];
		for (int employee = 0; employee < N; employee++) {
			st = new StringTokenizer(br.readLine());
			int taskSize = Integer.parseInt(st.nextToken());
			for (int i = 0; i < taskSize; i++) {
				int task = Integer.parseInt(st.nextToken());
				edge[employee][task-1] = 1;
			}
		}

		int ret = bipartiteMatching();
		System.out.println(ret);

	}
	public static int bipartiteMatching(){
		matched = new int[M]; Arrays.fill(matched, -1);

		int totalMatching = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 2; j++) {
				visited = new boolean[N];
				if(searchAugmentPath(i)) {
					totalMatching++;
				}
			}
		}

		return totalMatching;
	}

	private static boolean searchAugmentPath(int employee) {
		if(visited[employee]) return false;
		visited[employee] = true;

		for (int task = 0; task < M; task++) {
			if(edge[employee][task] == 1) {

				if(matched[task] == -1 || searchAugmentPath(matched[task])) {
					matched[task] = employee;
					return true;
				}
			}
		}

		return false;
	}

}

 

 

포드-풀커슨 버전

package backjoon.networkflow.bipartitematching.p11376;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

/*
자바쟁이 - https://javachoi.tistory.com/

백준 11376번 - 열혈강호2
https://www.acmicpc.net/problem/11376

포드-풀커슨 version
 */
public class MainVersion2 {
	static int N,M,V, INF=987654321;
	static int[][] capacity, flow; // [직원][작업]
	public static void main(String[] args) throws Exception {
//		BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
		V = N+M+2;
		capacity = new int[V][V];
		flow = new int[V][V];
		for (int employee = 0; employee < N; employee++) {
			st = new StringTokenizer(br.readLine());
			int taskSize = Integer.parseInt(st.nextToken());
			for (int i = 0; i < taskSize; i++) {
				int task = Integer.parseInt(st.nextToken())-1;
				capacity[employee+2][N+task+2] = 1;
			}
		}

		networkModeling(capacity);
//		Arrays.stream(capacity).forEach(arr -> System.out.println(Arrays.toString(arr)));

		int ret = getMaxFlow(0,1);
		System.out.println(ret);
	}

	private static int getMaxFlow(int source, int sink) {
		int totalFlow = 0;

		while(true) {
			//증가 경로 찾기
			int[] parent = new int[V]; Arrays.fill(parent, -1);
			parent[source] = source;
			Queue<Integer> q = new ArrayDeque<>();
			q.add(source);
			while(!q.isEmpty() && parent[sink] == -1) {
				int here = q.poll();
				for (int there = 0; there < V; there++) {
					if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1) {
						q.add(there);
						parent[there] = here;
					}
				}
			}
			//증가 경로가 없으면 종료한다
			if(parent[sink] == -1) break;
			//증가 경로를 통해 유량을 얼마나 보낼지 결정한다.
			int amount = INF;
			for (int p = sink; p != source ; p = parent[p]) {
				amount = Math.min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
			}

			//증가 경로를 통해 유량을 보낸다.
			for (int p = sink; p != source; p = parent[p]) {
				flow[parent[p]][p] += amount;
				flow[p][parent[p]] -= amount;
			}

			totalFlow += amount;
		}
		return totalFlow;
	}

	private static void networkModeling(int[][] capacity) {
		//source -> 직원 간선 추가(용량=2)
		for (int i = 0; i < N; i++) {
			capacity[0][i+2] = 2;
		}

		//작업 -> source 간선 추가(용량=1)
		for (int i = 0; i < M; i++) {
			capacity[N+i+2][1] = 1;
		}
	}
}

 

 

재귀를 이용한 이분 매칭이 어쩌면 느리지 않을까? 라고 내심 생각했지만 이분 매칭 알고리즘이 두배 정도 빨랐다.

이분 매칭은 4초대, 포드-풀커슨은 8초대에 통과했다.(문제의 시간 제한은 4초지만 자바라서...)

 

간단하게 시간 복잡도를 살펴보니 이분 매칭은 O(VE), 포드-풀커슨은 O(V*E^2)다.

이분 매칭의 시간 복잡도가 VE라는걸 이해하기는 어렵지 않았지만 포드-풀커슨의 시간 복잡도 계산은 이해가 안간다.

알고리즘 자체가 그래프에서 증가 경로가 발견되지 않을 때까지 반복하는 방식이라 계수에 왜 E^2항이 들어있는지 모르겠다