Dev_Diary

https://www.acmicpc.net/problem/11405지난 문제와 같이 최소 비용 최대 유량 문제입니다.SPFA 알고리즘과 네트워크 플로우 알고리즘을 함께 사용해 풀었습니다.최대 비용을 구할 때 전달된 책의 수를 곱해주어야 합니다. import sysfrom collections import dequeinput = sys.stdin.readline# SPFAdef spfa(start, N, M, graph, flowable): # 방문 목록 visited = [-1 for _ in range(1+M+N+1)] visited[start] = start # 최단거리 min_dists = [float('inf') for _ in range(1+M+N+1)] min_..

https://www.acmicpc.net/problem/14286최대 유량 최소 컷 정리를 이용한 최대 유량 문제입니다.최소 컷을 구하기 위해 간선을 차단할 때는 경로 중 가장 코스트가 작은 간선을 차단합니다.그 과정이 최대 유량 문제에서 유량을 흘릴 때 경로에서 가장 작은 코스트를 흘려주는 것과 같기 때문에 결국 최소 컷 문제의 해와 최대 유량 문제의 해는 같다고 볼 수 있습니다. 다만 양방향 간선이기 때문에 노드를 들어오는 노드와 나가는 노드로 쪼개어 풀면 수월하게 풀 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(n, m, edges, s, t): # 최대 유량 최소 컷 # 최소 컷..

https://www.acmicpc.net/problem/11408열혈강호 시리즈 다섯번째 문제입니다.이번 문제 또한 최대 유량 문제이지만 그 중에서 최소 코스트를 구하는 최소 비용 최대 유량(MCMF) 문제 입니다. 거창한 이름과는 다르게 해결 방법은 크게 새롭지 않습니다. 최대 유량 문제에서 길을 탐색할 때 모든 엣지의 코스트가 1 이었기 때문에 BFS 를 사용해 단순히 경로만 파악했다면 코스트가 생겼기 때문에 최단 코스트가 발생하는 경로를 찾아주면 됩니다. 최단 경로를 구한다면 가장 간단하게 다익스트라 알고리즘을 생각할 수 있지만 최대 유량 문제에서 코스트를 계산할 때에는 음의 경로로 이동할 경우 음의 코스트를 더해주어야 하기 때문에 다익스트라는 사용할 수 없습니다. 때문에 음의 경로가 존재해도 경..

https://school.programmers.co.kr/learn/courses/30/lessons/258709?language=python3모든 경우의 수를 계산해보면 풀 수 있는 문제입니다.combinations, prodect 함수를 잘 사용하면 상당히 짧은 코드로 풀 수 있습니다.또 이긴 경우의 수를 계산할 때, 이분탐색 라이브러리인 bisect 를 사용하면 보다 편하게 구할 수 있습니다.from itertools import combinations, productfrom bisect import bisect_leftdef solution(dice):    # 주사위의 개수    n = len(dice)    # 주사위들의 경우의 수    dices_case = list(product(rang..

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/15681트리를 순회하는 문제입니다.우선 양방향 그래프를 구성한 뒤 루트 노드에서 시작해 BFS 를 통해 트리를 만들어줄 수 있습니다. 자손의 수는 자식의 자손의 수를 모두 합한 것에 자식의 수를 합친 것과 같습니다.즉 더 작은 경우로 나누어 계산할 수 있고 DP 로 풀 수 있습니다.import sysfrom collections import dequesys.setrecursionlimit(1000000)input = sys.stdin.readline# 자식 노드의 수를 찾는 함수def cal_child(tree, childs, node):    # 자손의 수가 구해져 있지 않으면    if childs[node] 0:        # 자식이 없..