6181번 - 플러드 필 (Flood Fill) 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 383 | 93 | 77 | 33.624% |
문제
재현이는 얼마 전, 그래프 탐색에 대해서 배웠다. 강의를 맡은 지학이는 그래프 탐색을 통해서 풀 수 있는 대표적인 문제인 Flood Fill에 대해서 알려주었다.
- N * N 격자에 M개의 점이 있을 때, 상하좌우에 붙어있는 인접한 셀을 연결되어 있다고 하자, 연결되어 있는 점들의 집합을 “섬” 이라고 부르면, 섬의 개수와, 가장 큰 섬의 크기는 얼마인가?
이 문제를 푸는 법은 여러 방법이 있지만, 재현이는 깊이 우선 탐색으로 문제를 풀었다. 재현이는 점들을 정점이라 생각하고, 연결되어 있는 점들 사이에 간선을 이으면, 그래프의 컴포넌트의 개수와, 가장 큰 컴포넌트의 크기를 묻는 문제로 변환됨을 알아냈다. 재현이는 이를 깊이 우선 탐색으로 구한 후 지학이에게 자랑하였다.
지학이는 재현이가 이 문제를 푼 것을 본 후 감탄하여, 문제를 조금 더 어렵게 해서 주었다.
- N은 무조건 1,000,000,000이다. 고로 격자의 크기는 1,000,000,000 * 1,000,000,000 크기이다.
- (x1, y1) 점과 (x2, y2) 점의 “택시 거리” 는 |x2 - x1| + |y2 - y1| 으로 정의된다. 이 정의대로라면 상하좌우에 인접한 셀은 택시 거리가 1 이하인 셀의 쌍이었다는 것을 알 수 있다. 지학이는 “붙어있다” 의 정의를 바꿨다
- 택시 거리가 1 이하가 아니라, 택시 거리가 D 이하이면 붙어 있는 것이다.
이 문제는 갓 그래프 탐색을 배운 재현이에게 너무 어려운 문제였고, 재현이는 여러분들에게 도움을 요청했다. 재현이를 도와주자!
입력
첫 번째 줄에 M과 D가 주어진다. (1 <= M <= 100,000, 1 <= D <= 1,000,000,000)
이후 M개의 줄에 점의 좌표 Xi, Yi가 주어진다. (1 <= Xi, Yi <= 1,000,000,000)
출력
지학이가 어렵게 바꾼 문제의 정의대로, 섬의 개수와 가장 큰 섬의 크기를 출력하라.
예제 입력 1
4 2 1 1 3 3 2 2 10 10
예제 출력 1
2 3
힌트
(1,1) - (3,3) - (2,2) 셀은 연결되었으며, (10, 10) 셀은 혼자이다. 섬의 개수는 2개이고, 가장 큰 섬은 크기가 3이다.
출처
Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO US Open 2008 Contest > Gold 3번
- 문제를 번역한 사람: koosaga
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호