만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

둘러싸인 영역

면접 대비

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

요약
격자에 검은 말뚝과 흰 말뚝, 빈 칸이 주어질 때, 검은 말뚝에서 빈 칸만 거쳐 닿을 수 있고 흰 말뚝과 인접하지 않은 칸의 수, 그리고 그 반대 경우의 수를 구합니다.
난이도

보통10점 중 4점

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

문제

두 부동산업자가 여객선을 타고 남쪽 섬으로 향하고 있었다. 파란 하늘, 상쾌한 바람…. 두 사람은 다른 승객들과 함께 뱃길을 즐기고 있었다. 그런데 어느 날 갑자기 일어난 회오리바람 때문에 여객선이 가라앉고 말았다. 다른 승객들은 구조대에 구조되었지만, 어찌 된 일인지 이 두 사람만 눈에 띄지 않아 빠지고 말았다. 며칠을 표류한 끝에 두 사람은 어떤 무인도에 흘러들어 갔다. 이 무인도는 직사각형이고, 아래 그림처럼 격자로 나뉘어 있었다.

그림 C-1: 무인도의 모양

두 사람은 매우 욕심이 많았으므로, 구조를 요청하는 대신 이 무인도의 땅을 팔 생각을 했다. 그리고 땅을 반으로 나누지 않고 땅을 차지하려는 다툼을 시작했다. 두 사람은 각자 자기 땅으로 삼고 싶은 곳을 한쪽은 검은 말뚝으로, 다른 쪽은 흰 말뚝으로 둘러싸기 시작했다. 모든 말뚝은 격자의 중앙에 박혔고, 한 격자에 여러 개의 말뚝이 박히는 일은 없었다. 얼마 지나자 양쪽 모두 지쳐서 말뚝을 박는 것을 그만두었다.

당신이 할 일은 검은 말뚝과 흰 말뚝으로 둘러싸인 땅의 넓이를 구하는 프로그램을 작성하는 것이다. 격자 (i,j)(i, j)가 검은 말뚝으로 둘러싸여 있다는 것은 직관적으로 "격자 (i,j)(i, j)에서 위아래좌우로 임의로 이동할 때 처음 만나는 말뚝이 항상 검은 말뚝이다"라는 뜻이다. 정확하게는 다음과 같이 정의한다.

검은 말뚝에 "확대 인접한" 격자는 다음과 같이 정한다. 흰 말뚝에 대해서도 마찬가지로 정한다.

  • 격자 (i,j)(i, j)에 말뚝이 없고, 격자 (i,j)(i, j)에 인접한 격자 가운데 하나에 검은 말뚝이 있으면, 격자 (i,j)(i, j)는 검은 말뚝에 확대 인접해 있다.
  • 격자 (i,j)(i, j)에 말뚝이 없고, 격자 (i,j)(i, j)에 인접한 격자 가운데 하나가 검은 말뚝에 확대 인접해 있으면, 격자 (i,j)(i, j)는 검은 말뚝에 확대 인접해 있다. 이 규칙은 재귀적으로 적용된다.

이때 격자 (i,j)(i, j)가 검은 말뚝에 확대 인접해 있고 흰 말뚝에 인접해 있지 않을 때, 그리고 오직 그때에만 격자 (i,j)(i, j)가 검은 말뚝으로 둘러싸여 있다고 한다. 반대로 격자 (i,j)(i, j)가 흰 말뚝에 확대 인접해 있고 검은 말뚝에 인접해 있지 않을 때, 그리고 오직 그때에만 격자 (i,j)(i, j)가 흰 말뚝으로 둘러싸여 있다고 한다.

입력

입력은 여러 데이터셋으로 이루어진다. 각 데이터셋의 구성은 다음과 같다.

w h
a1,1 a2,1 a3,1 ... aw,1
a1,2 a2,2 a3,2 ... aw,2
...
a1,h a2,h a3,h ... aw,h

ww는 땅의 가로 길이, hh는 땅의 세로 길이를 나타낸다. 이 값은 1≤w,h≤501 \le w, h \le 50을 만족한다. 각 ai,ja_{i,j}는 격자 (i,j)(i, j)의 상태를 나타내는 반각 문자 하나이며, B는 검은 말뚝이 박혀 있음을, W는 흰 말뚝이 박혀 있음을, .(마침표)은 어느 말뚝도 박혀 있지 않음을 나타낸다.

w=h=0w = h = 0은 입력의 끝을 나타내며, 데이터셋에는 포함되지 않는다.

출력

각 데이터셋에 대해 검은 말뚝이 둘러싼 땅의 크기와 흰 말뚝이 둘러싼 땅의 크기를 하나의 공백으로 구분하여 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    10 10
    .....W....
    ....W.W...
    ...W...W..
    ....W...W.
    .....W...W
    ......W.W.
    BBB....W..
    ..B..BBBBB
    ..B..B....
    ..B..B..W.
    5 3
    ...B.
    ...BB
    .....
    1 1
    .
    0 0
    
    예상 출력
    6 21
    12 0
    0 0