꿀벌 문제

면접 대비

시간 제한2초메모리 제한512 MB

요약
벌집 격자에서 굳은 칸과 빈 칸이 주어진다. 빈 칸에 꿀을 붓고 인접한 빈 칸으로 번지게 하여 h 단위를 저장할 때 직접 붓는 횟수의 최솟값을 구한다.
난이도

보통10점 중 7점

유형
그래프, BFS, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

당신은 열심히 일하는 꿀벌이고, 고민이 하나 있습니다. 하루 종일 꿀을 모은 뒤 커다란 꿀을 가지고 벌집으로 돌아가는 중입니다. 지금 당장 낮잠을 자고 싶지만, 아쉽게도 먼저 벌집에 꿀을 모두 저장해야 합니다. 벌집의 칸을 열어 꿀을 붓는 데는 시간이 많이 걸리므로, 이 작업을 최대한 적게 하고 싶습니다.

벌집의 일부 칸에는 이미 굳은 옛 꿀이 차 있습니다. 나머지 칸은 아직 비어 있습니다. 빈 칸에 꿀을 부으면 꿀은 자동으로 인접한 빈 칸으로 흘러갑니다. 그 칸들에서 다시 다른 인접한 빈 칸으로 흘러갑니다. 덕분에 그 칸들에는 꿀을 직접 붓지 않아도 됩니다. 당신은 이 성질을 이용해, (간접적으로) 인접한 빈 칸이 많은 칸에 꿀을 붓기로 합니다.

그림 1: 처음 두 예제의 벌집. 검은 육각형은 이미 굳은 꿀이 들어 있는 칸입니다. 흰 칸은 아직 비어 있습니다.

당신에게는 몇 단위의 꿀이 있고, 벌집의 배치를 알고 있습니다. 꿀을 부을 칸을 영리하게 고르면, 해야 할 일의 최소량은 얼마입니까?

입력

입력의 첫 줄에는 세 정수 0≤h≤1060 \le h \le 10^6 (가지고 있는 꿀의 양)과 1≤n,m≤1031 \le n, m \le 10^3 (격자의 크기)이 주어집니다.

그다음 nn개의 줄이 주어지며, 각 줄은 격자의 한 행입니다. 각 행에는 빈 칸을 나타내는 . 또는 채워진 칸을 나타내는 # 중 하나가 mm개 있고, 기호들은 공백으로 구분됩니다. 또한 두 번째 행마다 약간 오른쪽으로 어긋나 있으므로 맨 앞에 공백이 하나 있습니다.

격자에는 항상 꿀을 모두 저장할 만큼 빈 칸이 있습니다.

출력

벌집에 꿀을 모두 저장하기 위해 꿀을 직접 부어야 하는 칸의 수를 정수 하나로 출력합니다.

예제2

  1. 예제 1

    입력
    8 4 4
. # # .
 # . # .
# # # .
 # . . .
    예상 출력
    3

  2. 예제 2

    입력
    6 3 6
. . # # . .
 . . # # . #
# # # . # #
    예상 출력
    2