Red Salmon

출처: https://www.acmicpc.net/problem/2188

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/2188.cpp

이번주 내내 공부했던 알고리즘이다. 드디어 문제에 적용시켜보았고 풀었다. 아직 완벽히 내것으로 만든건 아닌것 같다. 그렇기 때문에 나의 이해가 틀릴수도 있다고 생각한다. 

먼저 내가 가장 많이 참고한 사이트는 여기를 들어가면 볼 수 있다.  약 20번정도 읽은 것 같다. 소스는 그냥 외워질정도로 많이 봤다. 

먼저 간략히 설명하면 이분매칭은 두개의 그룹이 있을때 서로 매칭을 시키는데 단순 DFS를 하면 굳이 하지 않아도 될 검사들을 많이 하는데 이를 전부 빼버리고 한번에 연결하고자 할때 쓰는 방법이다. 

인터넷을 찾아보면 참 많은 사진과 글들이 나오는데 나는 나만의 방법대로 쓰겠다.

용도

1. 일단 두개의 그룹이 주어지고 조건에 따라 그룹이 최대의 매칭을 찾아야 하는 경우

2. DFS나 BFS같은 탐색 문제 같은데 시간초과가 나오고, 묹데는 결국 매칭을 찾아 특정 어떤 값을 찾아야하는경우(값을 찾는건 알고리즘과는 별개로 새로운 방법을 도입해야 한다.)

대강 이정도로 이해하고 있으면 용도를 알게 될 것이다. 이 문제는 1번의 경우이다. 

이 문제 역시 결국 축사라는 그룹과 소라는 그룹이 있고 이 두 그룹이 소의 축사 선호도에 따라 매칭을 시켜주는 것이다.  

소스를 보며 자세히 살펴보면 입력은 일반적인 그래프와 동일하다. like에서 -1을 해주는것은 입력은 1부터 들어오지만 나는 0부터 사용을 할 것이기 때문이다. 

그리고 보면 함수 bmp가 있다 bmp는 Bipartite Matching 이라 bpm 인데 잘못쓴거다...

암튼 해당 함수의 목적은 매칭의 수를 검색하여 리턴해주는 것이다. 즉 이 함수의 리턴값이 최대 매칭 수가 되는 것이다. 처음 fill을 사용하여 bmatch를 -1로 초기화하였는데 해당 배열은 한번이라도 이 값이 사용이 되었는지 아닌지를 체크하기 위함이고 처음 호출시 당연히 모든 값이 사용되지 않았기 때문에 -1이 된다. 

그후 n만큼 체크를 하는데 이는 A그룹의 처음과 끝을 의미하게 된다. 각 그룹마다 인덱스 값을 dfs함수에 넘겨주게 된다. 그 전에 chk는 bmatch와 다른데 bmatch는 전체적으로 볼때 한번이라도 사용을 했는지 안했는지를 판단하게 되고, chk는 해당 싸이클에서 사용이 되는지 안되는지를 체크한다. 그러므로 각 인덱스마다 초기화를 해주어야 맞다. 이 차이는 dfs함수를 보면 이해가 빠르다.

dfs함수는 우선 bfs로도짤수있고 다양한 방법이 존재한다. 그러나 어떤 글쓴이의 말에 의하면 대부분의 문제는 dfs로도 풀린다고 한다. 뭐 간혹 bfs를 요구하는 문제가 있다고 하는데 그냥틀리련다...

dfs함수를 보면 처음 if문은 현재 인덱스값이 사용이 되었는지를 판단하게 되고, 사용되었다면 리턴값을 주고 아니라면 사용했다고 체크를 하게 된다. 그리고 현재 인덱스 값에서 연결된 간선을 조사하게 된다.

next는 해당 위치에서 연결된 B그룹의 인덱스 를 의미하게 된다. 

그리고 나오는 if는 우선 bmatch를 체크하는건 한번도 사용이 안되었다면 사용을 함으로써 매칭이 이루어진다는 것을 의미한다. 그게 아니라면 dfs에 bmatch[next] 값을 주어 다시 검사를 한다. 이것이 결국 매칭이 안되는 녀석으로 온다면 매칭이 끝내 성공하게 되는 것이다. 더 깊게 설명하기는 힘들다. 직접 작은 테스트케이스를 잡고 실험해보는게 좋다. 

안에서는 bmatch[next]에 현재 인덱스 즉 pos값을 주어 bmatch가 결국 현재 인덱스와 매칭이 되고 있음을 알려주고 트루를 리턴해준다.  결국 bpm에서는 트루를 리턴을 받으니 매칭이 성공했다고 인식하고 match를 하나 올려주게 된다. 

bpm에서 i가 0부터 시작했으니 1이되면 다시 1을 기준으로 시작한다. 하지만 bmatch는 변하지 않는데 그 이유는 이 녀석은 결국 0번에서 체크가 이루어진 결과를 담고 있다고 보면 되기 때문이다.(즉, 이 녀석이 담고 있는 값은 큰 의미가 없다. 그저 해당 인덱스가 어떤 인덱스와 매칭이 이루어졌다. 이것이 다일뿐이다.) chk만 현재 인덱스를 기준으로 사용되지 않는 결과를 담고 있다고 보면 된다.

결국은 두개의 그룹이 서로 왔다갔다 하는것이다.

상당히 어려운 알고리즘이라고 생각한다.

출처 : https://www.acmicpc.net/problem/1587

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1587.cpp

음..나는 이분매칭을 공부하려고 이문제를 열었으나, 이 문제는 이분매칭과는 조금 거리가 있어보인다.

풀이도 전혀 상관없어보인다.

문제가 상당히 어렵게 풀어져있는데 핵심은 매우 간단한 것이다. 하지만 나는 찾지 못하였고 구글링을 통해 문제를 이해하였다.

접근방법

1. 우선 A라는 집합안에서도 매칭이 가능하다. 그리고 답은 최대 매칭을 구하는 것이다. 그렇다면 기본적으로 각 집합을 2로나눈 값을 더한게 최대 매칭이 된다. (하단에 위치한 연결간선은 최대매칭을 해봐도 집합안에서 하는것보다 작게 나온다.)

2. 만약 A또는 B 둘 중 하나가 홀수고 하나는 짝수라면 결국 한녀석은 마지막까지 선택이 되지 않으므로 무시한다.

3. 하지만 둘다 홀수라면 2개씩 짝지어도 하나씩 남는다. 여기서 만약 하단에 입력으로 홀수에서 홀수로가는 간선이 하나라도 존재하면 모두 연결이 되는 것이고, 홀수에서 짝수로만 가거나 짝수에서 짝수로만 가게 된다면 결국 남게 되는 것이다. 그래서 모두 연결되었을때 +1을 해주면 답이 나온다.

예시를 들어보겠다.

A 가 3이고 B가 3이라고 가정하자.

하단의 매칭 부분에서 1->3 혹은 1->1 혹은 3->3 이 존재하면 +1의 경우가 생기는 것이고 나머지 녀석들은 볼필요도없이 나누기 2를 하면 매칭수가 나오게 된다. 

그런데 만약 연결이 1->2 혹은 3->2 혹은 2-> 모든수 라면 동일 집합에서 연결할수 있는 경우가 사라지게 된다. 문제에서 분명 연속된 수끼리만 연결이 된다고 하였으니 불가한 경우가 된다. 다음의 문장을 명심해야한다.

거의 이분 그래프는 이분 그래프와 다르게 nA-1 + nB-1개의 간선을 추가로 가진다. 추가가 되는 간선은 Ai에서 Ai+1로 가는 간선 (1 ≤ i ≤ nA-1)과 Bi에서 Bi+1로 가는 간선 (1 ≤ i ≤ nB-1)이다.

위 문장에 따라 연결이 끈기게 되므로 필요가 없어진다. 그래서 반드시 홀수끼리 연결이 되야 한다. 

실로 간단한 문제이나, 문제가 어렵게 설명된거 같은 느낌이다.