Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 빅스비
- 완전탐색
- 빅스비 스튜디오
- JOIN
- INNER JOIN
- SWEA
- 프로그래머스
- SQL
- SDS 알고특강
- 삼성
- BOJ
- SWTest
- 이분탐색
- 분할정복
- Network Flow
- 최대 유량
- Baekjoon
- 메모이제이션
- 네트워크 플로우
- maximum flow
- 백준
- DP
- ICPC
- bixby studio
- backjoon
- 후기
- 코딩테스트
- 알고리즘
- 세그먼트트리
- 최대유량
Archives
- Today
- Total
답은 알고리즘 뿐이야!
[BOJ 2414] 게시판 구멍 막기 본문
문제 출처 : https://www.acmicpc.net/problem/2414
2414번: 게시판 구멍 막기
첫째 줄에 N, M(1 ≤ N, M ≤ 50)이 주어진다. 다음 N개의 줄에는 M개의 문자로 게시판의 모양이 주어진다. 각각의 문자는 붙어 있으며, 구멍이 없는 부분은 '.', 구멍이 있는 부분은 '*'으로 주어진다.
www.acmicpc.net
풀이 :
네트워크 플로우 최대 유량 문제입니다.
구멍이 없는 부분에는 테이프를 붙이면 안되므로
행과 열에 대해 구멍이 연속적으로 있는 부분을 묶어서 인덱스를 만들어 주시고
구멍이 있는 부분의 좌표(y,x)에 대해 행과 열의 인덱스를 Capacity가 1로 이어 주시면 됩니다.
'알고리즘 > 백준문제풀이' 카테고리의 다른 글
[BOJ 2365] 숫자판 만들기 (0) | 2020.09.03 |
---|---|
[BOJ 1760] N-Rook (0) | 2020.09.03 |
[BOJ 5651] 완전 중요한 간선 (0) | 2020.09.03 |
[BOJ 10319] 좀비 아포칼립스 (0) | 2020.08.18 |
[BOJ 13505] 두 수 XOR (0) | 2020.08.17 |
Comments