이코테의 음료수 얼려먹기 문제랑 거의 동일한 문제이다.
문제의 포인트는 일단 우리 병사와 적국 병사의 그룹, 그리고 각 그룹의 인원수를 파악해야 하는 것인데 이는 bfs로 쉽게 구할 수 있다. (물론 dfs로도 풀이 가능)
bfs 동작 과정은 아래와 같으며, 아직 bfs와 dfs 개념 자체가 선명하지 않다면 이 포스팅을 읽어보고 오는 것을 추천한다.
arr[y][x]
) cur 변수에 저장한다.cnt+=1
)from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = []
for _ in range(m):
arr.append(list(input().strip()))
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(y, x):
q = deque()
q.append((y, x))
cur = arr[y][x]
arr[y][x] = 1 # 방문했음을 의미
cnt = 0 # 시작 ~!
while q:
y, x = q.popleft()
cnt += 1
for dy, dx in d:
Y, X = y + dy, x + dx
if (0 <= X < n) and (0 <= Y < m) and arr[Y][X] == cur:
q.append((Y, X))
arr[Y][X] = 1
return cnt
w_cnt = 0
b_cnt = 0
for i in range(m):
for j in range(n):
# bfs()로 반환된 cnt는 적군, 아군에 따라 따로 위력을 계산해준다.
if arr[i][j] == "W":
w_cnt += bfs(i, j) ** 2
elif arr[i][j] == "B":
b_cnt += bfs(i, j) ** 2
print(w_cnt)
print(b_cnt)
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dy, dx in d
Y = dy+y
X = dx+x