[백준] 22960. 미팅

newbieski·2021년 11월 23일
0

백준

목록 보기
50/210

https://www.acmicpc.net/problem/22960

요약

접근법

  • 공식 해설을 보고 해결함
  • 이분매칭으로 perfect 매칭인지 확인하고
  • perfect 매칭이면 -1
  • 그렇지 않으면 매칭 결과를 이용해서 역방향 간선을 생성한 후
  • 매칭에 사용되지 않은 왼쪽 노드로부터 연결되는 모든 왼쪽 노드를 찾는다.
    • 매칭에 사용되지 않은 노드의 오른쪽 노드가 비어있거나(비어있으면 매칭을 했었을 테니까), 매칭에 사용안된 노드와 연결이 매칭이 되거나(모순)는 아님
    • 매칭에 사용되지 않은 노드는 이분매칭 과정에서 사용이 안되었고, 오른쪽 노드는 다른 노드와 매칭에 사용된 점일 것이므로 연결 연결 하다보면 왼쪽이 +1 되는 개념인듯
    • 정확히는 모르겠고, 증명은 모르겠다. 공부해야함

다른 접근법

  • 오른쪽 노드 중에서 진입점이 0인 것들을 제외하고, 1인 것들은 연결된 왼쪽 노드를 제거하고, 다시 갱신하고... 를 반복해서 접근해보았는데 실패 발생
  • 이분 탐색 문제들이 이렇게 그리디스럽게 접근하면 다 실패였음
profile
newbieski

0개의 댓글