Dev_Diary

https://www.acmicpc.net/problem/2051역시 최소 버텍스 커버 + 이분매칭 문제입니다.다만 이분매칭을 단순히 활용하는 문제가 아닌 좀 더 본질에 가까운 문제라고 할 수 있습니다.바로 최소 버텍스 커버의 해 자체를 구하는 문제이기 때문입니다. 즉 최소 버텍스 커버 문제를 만족하는 노드들을 구하는 문제입니다.이는 쾨닉의 정리에 포함되어 있는 부분인데 방법은 이렇습니다. 1. 이분매칭을 통해 매칭되는 노드 / 엣지를 구합니다.2. 엣지를 뻗어 나가는 노드군을 L / 엣지가 도달하는 노드군을 R 이라고 했을 때, L 에 속한 노드 중 매칭되지 않은 노드를 L*, R 에 속한 노드 중 매칭된 노드를 R* 이라고 정하고 구해줍니다.3. L* 에서 시작해 연결된 노드들을 순회할텐데, L* 에..

https://www.acmicpc.net/problem/2414최소 버텍스 커버 문제 + 이분매칭 문제입니다. Python" data-og-description="https://www.acmicpc.net/problem/1867'해당 문제는 이분매칭 알고리즘을 사용하는 문제입니다.'라고 말하면 왜인지 다들 화가 날 것 같습니다. 저는 화가 났습니다. 왜냐하면 이 문제는 단순한 이분매칭 " data-og-host="dev-diary-0717.tistory.com" data-og-source-url="https://dev-diary-0717.tistory.com/158" data-og-url="https://dev-diary-0717.tistory.com/158" data-og-image="https://..

https://www.acmicpc.net/problem/3713이번 문제도 최소 버텍스 커버 + 이분매칭 콤보 문제입니다.만날 수 있는 노드를 모두 찾은 뒤 해당 노드들을 제거하면 됩니다.import sysinput = sys.stdin.readline# 이분매칭def bimatch(idx, connectable, connected, visited):    # 이미 방문했으면 패스    if visited[idx]:        return False        # 방문 체크    visited[idx] = True    # 순회    for node in connectable[idx]:        # 만날 수 있거나 뺏을 수 있으면        if connected[node] 0 or bima..

https://www.acmicpc.net/problem/1014https://www.acmicpc.net/problem/11014해당 문제는 최소 버텍스 커버 문제입니다. 해당 문제에서 학생 -> 학생 의 버텍스 (엣지) 는 커닝의 가능성으로 볼 수 있습니다.즉 모든 버텍스를 커버하면 커닝의 가능성이 있는 모든 위치를 탐색하는 것과 동일합니다.그러므로 모든 버텍스를 커버하고 남는 자리에 학생을 앉히면 커닝을 당하거나 할 가능성이 없습니다. 해당 문제에서 특정 위치에 학생을 앉힌다고 가정하면 해당 학생과 같은 열에 있는 학생은 커닝을 당할일도 할 일도 없습니다. 즉 어떤 학생에게서 다른 학생에게 향하는 버텍스는 짝수 -> 홀수 / 홀수 -> 짝수 의 두 경우로 나뉩니다. 그러므로 해당 문제의 그래프는 홀..

https://www.acmicpc.net/problem/32349이분매칭을 사용해 풀 수 있는 문제입니다.어차피 목표 위치가 상하좌우 방향의 위치에 인접해 있는것이 아니면 두 번 이상 이동해야 하기 때문에 구슬을 들었다 놓는 경우와 이동 횟수가 같습니다. 즉 한 칸을 이동하는 경우에만 최적화를 한 뒤 나머지는 모두 들어서 옮기면 됩니다. 우리가 주목해야 하는 경우는 두 가지 인데1. 초기 위치에는 구슬이 있지만 구슬이 없기를 원하는 경우 2. 초기 위치에는 구슬이 없지만 구슬이 있기를 원하는 경우 우리는 1 -> 2 로 구슬을 옮기길 원하기 때문입니다. 즉 1 과 2 를 탐색해 정리한 뒤 1 과 2 의 인덱스가 인접해 있는 경우를 찾아 연결 가능 목록에 넣어줍니다.후에 이분매칭을 통해 최대한 많이 한번..

https://www.acmicpc.net/problem/2787 '수열의 특정 인덱스에 특정한 수들이 들어갈 수 있고 가능한 많은 수를 인덱스에 배치해라'즉 흔한 이분매칭 문제입니다. 다만 헷갈릴 수 있는 부분이 있다면'[x, y] 구간의 최대/최솟값이 v 이다' 라는 말은 [x, y] 구간에 v 가 꼭 존재해야 한다는 말입니다.또 나머지 구간에는 v 가 존재할 수 없다는 말과 같습니다.  이를 신경써서 항상 이분매칭을 풀던 것 처럼 노드 -> 노드 연결 가능성만 체크해주면 됩니다.import sysinput = sys.stdin.readline# 이분매칭def bimatch(idx, range_list, connected, visited, excluded_idxs):    # 이미 방문한 노드면 탐색..

https://www.acmicpc.net/problem/2191이분매칭 문제입니다.단순하게 연결된 노드만 구해준다면 기본적인 이분매칭입니다.import sysfrom math import sqrtinput = sys.stdin.readline# 이분매칭def bimatch(idx, connectable, connected, visited):    # 이미 방문한 노드면 탐색 안함    if visited[idx]:        return False    # 방문 체크    visited[idx] = True    # 탐색 가능한 노드 탐색    for node in connectable[idx]:        # 연결할 수 있거나 연결된 노드를 다른 노드로 옮길 수 있다면        if conne..

https://www.acmicpc.net/problem/3295해당 문제는 이분매칭으로 풀 수 있는 문제입니다.이분매칭 문제는 보통 왜 이분매칭으로 풀 수 있는지 이해하는게 어렵습니다. 문제에서 보면 선형 배열은 K-1 의 가치를, 링은 K 의 가치를 갖습니다.그런데 이 수치는 해당 배열과 링이 갖고있는 노드의 수와 같음을 알 수 있습니다.결국 해당 문제는 '노드끼리 가장 많이 연결할 수 있는 경우를 찾아라' 를 요구하고 있습니다. 또 선형배열과 링은 하나의 노드 안에 들어가는 엣지와 나가는 엣지가 모두 하나 이하로 존재합니다. 즉 연결된 모든 노드는 1 대 1 매칭이 된다는 말입니다. 정리해보자면 '노드를 연결할 건데 모든 노드끼리는 1 대 1로 매칭이 되고 해당 조건 아래에서 가장 노드를 많이 연결..

https://www.acmicpc.net/problem/1671유명한 이분매칭 문제입니다.살아남을 수 있는 상어수의 최솟값을 구하라는 말은 가장 많이 잡아먹힌 케이스를 구하라는 말과 같고 최대한 많이 매칭하라는 말과 같으므로 이분매칭으로 풀 수 있습니다. 한 마리의 상어가 두 마리 까지 잡아먹을 수 있다는 점에서https://dev-diary-0717.tistory.com/172의 열혈강호 2 와 비슷한 문제입니다.이번에는 포스팅한 방식이 아닌 그저 이분매칭을 두 번 돌리는 방식으로 풀었습니다.또 주의해야 할 케이스가 서로를 잡아먹는 케이스인데, visited 를 조작하는 방식보다는 데이터를 서로 잡아먹을 수 없게 만들어놓는 것이 보다 편합니다.import sysinput = sys.stdin.read..

https://www.acmicpc.net/problem/1017소수 체크와 이분매칭을 합쳐놓은 문제입니다.우선 각 리스트의 요소에서 더하면 소수가 되는 목록을 만들어 노드간의 연결을 구해줍니다.그 뒤 이분매칭을 해주면 됩니다.전체에서 전체로 이분매칭을 하는 것이 왜 문제의 해답이 되는가 라고 생각할 수 있습니다.문제에서 제시된 첫 번째 예시를 예로 들겠습니다.  connected_with_first : 첫 번째 수가 연결된 수 / connected : 선택된 수가 연결되어있는 인덱스    connected_with_first : 4 / connected : [3, 0, 1, 2, 5, 4]     connected_with_first : 10 / connected : [3, 2, 1, 0, 5, 4] ..