답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 �� www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 아래의 그림처럼 격자를 체스판처럼 나눠서 Source -> 빨간색 영역 -> 사방의 하얀색 영역 -> Sink 이런식으로 모델링 해 주시면 가로 세로 블럭에 대한 모델링은 완성입니다. 그 다음 최소 연산 횟수를 구해야 하는데 위의 모델링으로 구할 수 있는 연산 횟수는 " 둘다 양수인 격자에 대한 최소 ..

문제 출처 : https://www.acmicpc.net/problem/2365 2365번: 숫자판 만들기 입력의 첫째 줄에는 행(열)의 크기 N이 주어진다(1≤N≤50). 둘째 줄에는 N개의 정수가 주어진다. 주어지는 정수는 1행부터 N행까지의 합을 차례대로 나타낸다. 셋째 줄에는 N개의 정수가 주어진다 www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 아래의 그림 처럼 행과 열을 각 각 묶어서 모델링 하여 1번행 3번열을 묶으면 (1,1), 1번행 4번열을 묶으면 (1,2) 이런식으로 표현 될 수 있도록 모델링 합니다. 그 후 문제 조건에 따라 최대 숫자의 값을 최소로 하는 형태를 찾아야합니다. 이는 모든 엣지의 Capacity에 대해 Limit을 1 ~ 1000까지 걸어 ..

문제 출처 : https://www.acmicpc.net/problem/1760 1760번: N-Rook 첫째 줄에 격자의 크기를 나타내는 두 자연수 N, M이 주어진다. 격자가 N행 M열로 이루어져 있다는 의미이다. (1 ≤ N, M ≤ 100) 둘째 줄부터는 격자의 모양을 나타내는 정보가 한 줄에 한 행씩 주어 www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 0 : 빈 격자 1: 구덩이가 파인 격자 2: 벽이 놓인 격자 2020/09/03 - [알고리즘/백준문제풀이] - [BOJ 2414] 게시판 구멍 막기 [BOJ 2414] 게시판 구멍 막기 문제 출처 : https://www.acmicpc.net/problem/2414 2414번: 게시판 구멍 막기 첫째 줄에 N, M..

문제 출처 : https://www.acmicpc.net/problem/2414 2414번: 게시판 구멍 막기 첫째 줄에 N, M(1 ≤ N, M ≤ 50)이 주어진다. 다음 N개의 줄에는 M개의 문자로 게시판의 모양이 주어진다. 각각의 문자는 붙어 있으며, 구멍이 없는 부분은 '.', 구멍이 있는 부분은 '*'으로 주어진다. www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 구멍이 없는 부분에는 테이프를 붙이면 안되므로 행과 열에 대해 구멍이 연속적으로 있는 부분을 묶어서 인덱스를 만들어 주시고 구멍이 있는 부분의 좌표(y,x)에 대해 행과 열의 인덱스를 Capacity가 1로 이어 주시면 됩니다.

문제 출처 : https://www.acmicpc.net/problem/5651 5651번: 완전 중요한 간선 입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1

문제 출처 : https://www.acmicpc.net/problem/1031 풀이 : Maximum Flow 문제입니다. 아래의 조건에 따라 푸시면 됩니다. 1. A팀의 경기수 총합 != B팀의 경기수 총합 => -1 2. A팀의 경기수 총합 != Maximum Flow => -1 3. A팀의 경기수 총합 == Maximum Flow => 사전순 정렬 이문제의 핵심은 3번 사전순 정렬인데 사전순 정렬은 엣지 하나를 고르고 엣지와 동일한 시작점에서 동일한 끝점으로 갈수있는 다른 플로우가 있는지 찾은 후 있으면 엣지의 플로우를 지워주고 경로에 Flow를 흘려주시면 됩니다. 단 찾을때 정렬을 해야하기 때문에 시작점과 끝점의 범위에 주의해야합니다. 만약 인풋이 2 2 1 1 1 1 일때, 1->3, 2->4..

문제 출처 : https://www.acmicpc.net/problem/3640 풀이 : MCMF 문제입니다. 1 을 source, V 를 sink로 잡고 mcmf를 해주시면 되는데 조건중에 정점 중복이 없다라는 말이 있으므로 정점 분할을 하고 V번 정점에서 V ' 번 정점으로 가는 Capacity를 2로, S번 정점에서 S ' 번 정점으로 가는 Capacity를 충분히 준 후 MCMF를 돌리시면 됩니다. 아래는 2번째 인풋을 모델링 한 그림입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 ..

문제 출처 : https://www.acmicpc.net/problem/2367 풀이 : 네트워크 플로우 (Maximum Flow) 문제입니다. 파티에 N명의 사람이 오고 D개의 음식을 준비해야하는데 한 사람당 음식을 K개 준비할 수 있고 같은 음식은 1개만 준비할 수 있습니다. 따라서 다음과 같이 모델링 할 수 있습니다. 1. Source에서 사람으로 K만큼의 Capacity를 가진 Edge를 연결 2. 사람에서 각 사람당 준비할 수 있는 음식으로 1만큼의 Capacity를 가진 Edge를 연결 (한개의 음식은 한사람당 하나만 들고갈수 있으므로) 3. 각 음식에서 Sink로 가져올 수 있는 갯수만큼의 Capacity를 가진 Edge를 연결 예제의 경우를 네트워크 플로우로 모델링 하면 아래와 같은 모형이..