문제 1029 · 중급 5
서버실 랙 구역
DFS · BFS · 격자 · 연결 요소
테스트별 제한 2000ms · 브라우저 채점
문제
서버실 바닥 배치도가 R행 C열 격자로 주어진다. '#' 은 서버 랙이 놓인 칸, '.' 은 빈 칸이다. 위·아래·왼쪽·오른쪽으로 맞닿은 랙끼리는 같은 구역으로 묶이고, 이렇게 이어진 랙 전체가 하나의 구역이다. 대각선으로만 닿은 것은 이어진 것이 아니다. 구역이 몇 개인지와 가장 큰 구역의 랙 수를 구하라.
입력
첫째 줄에 R 과 C 가 주어진다. (1 ≤ R, C ≤ 300) 다음 R개 줄에 길이 C 인 문자열이 주어진다. 문자열은 '#' 과 '.' 로만 이루어져 있다.
출력
구역의 수와 가장 큰 구역의 랙 수를 공백으로 구분해 출력한다. 랙이 하나도 없으면 0 0 을 출력한다.
예제 입력 1
4 5 ##..# #..## ..#.. ##..#
예제 출력 1
5 3
힌트 펼치기
- 아직 방문하지 않은 랙을 만날 때마다 구역 수를 1 늘리고, 그 랙에서 이어진 랙을 모두 방문 표시하면서 개수를 센다.
- 구역 하나가 9만 칸이 될 수 있다. 재귀로 DFS 를 짜면 호출 깊이 제한에 걸리므로 스택이나 큐를 직접 쓰자.
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.