Dev_Diary

https://www.acmicpc.net/problem/9576오늘도 역시 이분매칭 기본 문제입니다.아래 문제들과 같은 문제이니 참고해주시면 좋을 것 같습니다.https://dev-diary-0717.tistory.com/170https://dev-diary-0717.tistory.com/171https://dev-diary-0717.tistory.com/172import sysinput = sys.stdin.readline# 이분매칭def bimatch(idx, hope_list, visited, connected):    # 이미 체크한 사람이면    if visited[idx]:        return False    # 체크    visited[idx] = True    # 원하는 책 목록 순..

https://www.acmicpc.net/problem/11375https://www.acmicpc.net/problem/11376열혈강호 1 의 경우 단순한 이분매칭입니다.https://dev-diary-0717.tistory.com/170https://dev-diary-0717.tistory.com/171두 문제와 상황과 입력만 다를 뿐 정확히 같은 문제이니 참고하시면 될 것 같습니다. 열혈강호 2 의 경우에는 한쪽이 담당할 수 있는 반대 노드가 n 개일 경우입니다.해당 경우에는 하나의 노드를 할당받을 수 있는 노드에서 n 개의 노드를 할당받을 수 있는 노드 쪽으로 이분매칭을 실행하면 됩니다. 다만 담당할 수 있는 업무가 n 개이므로 케이스를 n 개로 나누어 각각 처리해주면 됩니다. 이 외에도 일반..

https://www.acmicpc.net/problem/2188전형적인 이분매칭 문제입니다. Python" data-og-description="https://www.acmicpc.net/problem/1298전형적인 이분매칭 문제입니다.해당 알고리즘은 DFS 를 기반으로 합니다.우선 순차적으로 노드를 순회하며 매칭 가능한 노드를 연결합니다.다음 노드에서 임의의 노" data-og-host="dev-diary-0717.tistory.com" data-og-source-url="https://dev-diary-0717.tistory.com/170" data-og-url="https://dev-diary-0717.tistory.com/170" data-og-image="https://scrap.kakaoc..

https://www.acmicpc.net/problem/1298전형적인 이분매칭 문제입니다.해당 알고리즘은 DFS 를 기반으로 합니다.우선 순차적으로 노드를 순회하며 매칭 가능한 노드를 연결합니다.다음 노드에서 임의의 노드를 골랐는데 해당 노드가 이미 다른 노드와 연결되어있다면 연결된 노드를 다른 노드와 연결시킬 수 있는지 재귀적으로 탐색하며 최대한 옮긴 뒤 현재의 노드와 고른 노드를 연결시키는 방식입니다.조금 가볍게 말하자면 지하철을 탔을 때 임의의 자리에 앉고 싶을 경우 이미 앉아있는 승객에게 양해를 구해 다른 자리로 옮기게 하는 방식이라고 할 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readline# 이분 매칭def bima..

https://www.acmicpc.net/problem/1867이분매칭 알고리즘을 사용하는 문제입니다. 정확하게는 이 문제는 단순한 이분매칭 문제가 아닌 '최소 버텍스 커버(Minimum Vertex Cover)' 문제입니다. 최소 버텍스 커버란 무엇인지 먼저 짚고 넘어가겠습니다.어떠한 그래프가 있습니다.해당 그래프에서 몇 개의 정점을 고르겠습니다. 과연 몇 개의 정점을 골라야 그래프에 존재하는 모든 간선이 고른 정점과 연결되어 있을까요?해당 문제의 답을 찾는 것이 바로 최소 버텍스 커버 문제입니다. 그렇다면 문제는 왜 최소 버텍스 커버 문제일까요?행과 열을 나누어 각각 노드 그룹으로 쪼갠 뒤 돌이 있는 위치의 행 노드와 열 노드를 연결해 그래프를 만든다면 각 간선의 양 끝중 하나의 정점만 선택되어도..