[백준-파이썬] 1303: 전쟁 - 전투

문제로 가기~

BFS로 풀었다.
쭉~ 보면서 아직 방문 안한 곳이면 bfs로 상하좌우 4방향을 본다. 출발한 곳의 색깔과 같으면 개수를 더한다.
그래서 몇 명의 병사가 뭉쳐있는지 세고, 해당하는 팀에 힘(뭉친 수의 제곱!)을 더한다.
이미 센 병사는 또 세면 안 되니까 방문 체크

import collections
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(list(input().strip()) for _ in range(M))
dir_x, dir_y = [0, 0, -1, 1], [-1, 1, 0, 0]


def bfs(i, j, color):
    cnt = 1

    q = collections.deque()
    visited[i][j] = True
    q.append((i, j))

    while q:
        ii, jj = q.popleft()
        for k in range(4):
            ni = ii + dir_x[k]
            nj = jj + dir_y[k]

            if 0 <= ni < M and 0 <= nj < N and visited[ni][nj] == False:  # 범위, 방문 체크
                if arr[ni][nj] == color:
                    cnt += 1
                    visited[ni][nj] = True
                    q.append((ni, nj))
    return cnt ** 2


our_army_power = 0
their_army_power = 0
visited = [[False] * N for _ in range(M)]

for i in range(M):
    for j in range(N):
        if visited[i][j] == False:
            power = bfs(i, j, arr[i][j])
            if arr[i][j] == 'W':
                our_army_power += power
            else:
                their_army_power += power

print(our_army_power, their_army_power)