Red Salmon

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

정답 :  https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1298.cpp

이 문제는 그냥 이분매칭 알고리즘을 적용하면 풀리는 문제이다.

볼것도 없다. 최대 매칭을 구하라고하니 당연한 것이다. 알고리즘 역시 많이 썼던 그대로 하면된다.

그런데 항상 생각하는데, 쓰면 다 알고 보면 다 아는데 처음부터시작하면 오랜만에 하다보니 잘 기억이 나지 않고, 알고리즘이 쉽게 써지지 않는다. 더 많은 노력이 필요하다고 생각된다. 

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1298.cpp

요즘 날이 너무더워서 공부하기가 싫다. 책상에 앉으면 더워서짜증이 난다 ㅠㅠ 담엔 꼭 입사해야지..

이 문제는 결국 최대매칭을 찾는 문제이다. 즉 이분매칭문제이다. 어렵지 않았으나, 오랜만에 이 문제를 풀다보니 소스상의 실수가 있었고 이 실수를 찾기까지 정말 긴시간이 소요되었다. 

내가 한 실수는  if (bmatch[next] == -1 || dfs(bmatch[next])) 이부분에서 bmatch[next] 를 그냥 next만

넘겨버린 실수였다.

그래놓고 왜틀렸지? 생각만 엄청 했다. bmatch에는 현재 매칭된 녀석이 들어있거늘 나는 자꾸 다른 녀석을 주입하니 적은 테스트케이스였던 예제에서만 정답을 맞고 결론적으로는 오답이 나오는 것이다. 다음부터는 실수하지 말아야겠다 ㅠㅠ

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

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

이문제는 네트워크유량 문제이다. 즉 이분매칭이다. 

요즘 나는 이분매칭에 흠뻑 취해있다고 해도 과언이 아닐것이다. 그도 그럴게 하도 많이 틀려서 빡쳤다..결국 DFS인데..

암튼 이문제는 저번에 푼 축사배정문제와 완전히 똑같다고할수있다. 결국 최대매칭을 구하는 문제인데 소스마저 똑같다.

인풋이 똑같기 때문이다. 그냥 코딩연습이라 생각하고 풀었다.

문제는 어렵지 않다.

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

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

이 문제는 저번에 푼 이분매칭과 비슷한 문제이다. 이분 매칭, 최대유량, 네트워크플로우, 이분그래프 다 비슷한것 같다. 즉 어렵다... 완전히 내 지식이 되지 않은 것 같다.

우선 이 문제는 최대 정점이 2만개 최대 간선이 20만개다. 거기에 K가 최대 5까지 들어온다. 단순 계산만 22만번의 입력이 5번이 들어오니 총 110만번의 입력이 필요하다. 즉, cin쓰면 안된다. scanf를 써야 시간을 줄일 수 있다.

문제는 그냥 그래프를 주어졌을때 이것이 이분그래프인지 아닌지 판별하는 것이다. 이 문제를 나는 저번과 같은 생각을 하며 접근하면 답이 나올거라고 확신하였다. 

그러나 생각은 했으나 구현에는 실패하여 타인의 소스 도움을 받았다. 그리고 다시 작성하여 정답을 맞았다.

우선 알아두어야 할것은 이분 그래프이다. 즉 A아니면 B인것이다. 어떤 한 정점이 A로 가면 A와 연결된 녀석들은 B로 가야만 한다. 그런데 B로 갔는데 서로 연결이 되어 있으면 불가한 것이다. 이 부분만 명심하고 문제를 풀면 된다.

나는 우선 이를 복사한다는 개념으로 생각하여 A그룹과 B그룹이 모두 똑같다고 전제를 놓고 시작하였다. 그래서 check를 만들고 이미 사용된 녀석이라면 바로 스킵해가는 식으로 전개하였다. 하지만 사용하지 않았다면 dfs함수를 호출하는데 여기의 인자는 pos는 해당 위치인덱스이고 flag는 위에 말했던 A인가 B인가를 구별하기 위한것으로 초기 값은 크게 중요하지 않다. 

함수에서는 현재 인덱스값에 flag를 주고 그 연결된 간선의 크기만큼 포문을 돌린다. next를 할당하는데 next가 만약 flag와 같다면 같은 그룹에 속한다는 말이니 false를 리턴한다. 

하지만 만약 값이 아직 할당 전이라면 dfs를 다시 리턴하여 위 과정을 반복한다. 

그래서 check[next]의 값이 -1이지만 dfs가 트루를 보낸 경우와  check[next]의 값이 현재 flag와 다르다면 성공한 경우로 간주하고 다음으로 넘어가게 된다. 어떻게 보면 더 쉬운문제라고 할 수 있다. 이전 이분매칭과 다른점이 있다면

그 녀석은 A그룹 B그룹이 명확히 다르기 때문에 check를 2개를 두었다고 보면 된다. 아직 이런문제는 더 많이 풀어봐야 내것이 될 것 같다.