2개의 댓글이 있습니다.
-
-
Being -
이분 그래프: 그래프에 있는 모든 정점들을 두 그룹으로 나눴을 때, 모든 간선이 두 그룹을 서로 잇기만 하는 분할이 존재하는 그래프입니다. 이는 두 대상의 관계를 표현하는 셈입니다. 예를 들어, 보유한 전자 기기와 충전기 사이에 이 충전기에 충전 가능한가? 라는 관계를 둘 사이를 잇는 간선으로써 표현할 수 있습니다.
이분 매칭: 보유한 전자 기기와 충전기들로부터 최대 동시 몇 개의 전자 기기를 충전 가능한가? 라는 문제에 대한 해답입니다.
CCRICKET 문제의 경우, 2개짜리 타일을 최대한 많이 사용하는 것이 목표입니다. 격자판의 각 격자를 정점으로 생각해 봅시다. 이를 체스판과 같이 생각하면, 2개짜리 타일 하나는 인접한 검은 타일과 하얀 타일 하나씩을 덮게 됩니다. 따라서 검은 타일들의 정점과 하얀 타일들의 정점, 그리고 그 둘 사이에 인접 여부를 가지고 이분 그래프를 구성할 수 있습니다. 여기서 이분 매칭을 수행하면 서로 겹치지 않는 최대 타일의 수를 셀 수 있습니다.
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Freean2468
CCRICKET문제를 푸니 나꾸만 오답이 나오더군요
그래서 어떻게 풀어야 할까 검색해 보았는데 이분 매칭으로 풀면 된다고 합니다만, 모두 처음들은 용어들입니다.
이분 그래프가 뭔지는 검색해서 대충 알겠습니다만, 왜 이걸 이용해서 풀어야 하는지 도저히 감도 오질 않네요...
12년 전