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 | 31 |
Tags
- 빅스비 스튜디오
- Baekjoon
- 메모이제이션
- backjoon
- DP
- 최대유량
- ICPC
- INNER JOIN
- SQL
- JOIN
- SDS 알고특강
- BOJ
- 삼성
- 알고리즘
- 이분탐색
- 완전탐색
- 분할정복
- 프로그래머스
- SWEA
- 코딩테스트
- 네트워크 플로우
- Network Flow
- 백준
- 빅스비
- maximum flow
- 최대 유량
- 세그먼트트리
- 후기
- SWTest
- bixby studio
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 |
'알고리즘/백준문제풀이' Related Articles
more
Comments