8038 : 방 개수 세기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times M$ 크기의 격자 지도가 주어집니다. 각 칸은 비어 있거나(
방은 상하좌우로 인접한 비어 있는 칸들의 집합으로 정의됩니다. 지도 전체에서 방의 개수를 세는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N, M \le 1{,}000$
• 격자의 각 칸은 벽(
.) 벽(#)입니다.방은 상하좌우로 인접한 비어 있는 칸들의 집합으로 정의됩니다. 지도 전체에서 방의 개수를 세는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N, M \le 1{,}000$
• 격자의 각 칸은 벽(
#) 또는 바닥(.)입니다.입력 설명
첫째 줄에 격자의 세로 크기 $N$과 가로 크기 $M$이 공백으로 구분되어 주어집니다. ($1 \le N, M \le 1000$)
다음 $N$개의 줄에 각각 $M$개의 문자로 격자 지도의 정보가 주어집니다.
다음 $N$개의 줄에 각각 $M$개의 문자로 격자 지도의 정보가 주어집니다.
출력 설명
첫째 줄에 지도에 존재하는 방의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 8
########
#.#.####
#..#...#
#.##..##
########
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
이 문제는 격자형 그래프에서 연결 요소(Connected Components)의 개수를 세는 전형적인 그래프 탐색 문제입니다.
방문하지 않은 빈 칸(
방문하지 않은 빈 칸(
.)을 발견할 때마다 카운트를 1 증가시키고, DFS 또는 BFS 탐색을 시작하여 인접한 모든 빈 칸들을 방문 처리합니다. 전체 지도를 $O(N \times M)$ 시간에 스캔하여 답을 구할 수 있습니다.