양치기 꿍
면접 대비시간 제한1초메모리 제한128 MB
울타리로 나뉜 격자에서 연결된 영역을 탐색해 각 영역의 양과 늑대 수를 비교한 뒤 살아남는 양과 늑대의 총합을 구하는 문제입니다.
문제
양치기 꿍은 늑대들을 양이 있는 여러 울타리 안으로 몰아넣었다.
마당은 R행 C열의 격자로 주어진다. 빈칸은 ., 울타리는 #, 늑대는 v, 양은 k로 표시된다. 울타리(#)는 지나갈 수 없고, 양과 늑대는 상하좌우로만 같은 영역에 속한다. 대각선으로는 이동할 수 없다.
각 영역에서 양의 수가 늑대의 수보다 많으면 그 영역의 늑대는 모두 잡아먹힌다. 그렇지 않으면 그 영역의 양이 모두 잡아먹힌다.
모든 영역의 싸움이 끝난 뒤 살아남는 양과 늑대의 수를 구하라. 울타리로 막히지 않은 바깥 영역에는 양이나 늑대가 없다.
입력
첫째 줄에 영역의 세로 길이 R과 가로 길이 C가 주어진다. (3 ≤ R, C ≤ 250)
다음 R개의 줄에는 길이 C인 문자열이 주어진다. 각 문자는 ., #, v, k 중 하나이다.
출력
살아남는 양의 수와 늑대의 수를 이 순서대로 공백으로 구분해 출력한다.