답은 알고리즘 뿐이야!

문제 출처 : 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/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..