Red Salmon

출처 : 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개를 두었다고 보면 된다. 아직 이런문제는 더 많이 풀어봐야 내것이 될 것 같다.