[백준] 1303번 전쟁 - 전투 (by Python)

문제

https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

 

풀이

    전쟁터의 원소들을 하나하나 짚어나가면서 방문한 적이 없는 원소일 경우 방문해서 인접해있는 모든 같은 팀의 병사들을 BFS를 통해서 찾은 후에 병사들의 수를 제곱한 수를 해당하는 팀에 넣어준다. 그리고 나서 각 팀의 배열에 들어있는 수들을 모두 합해서 출력해주면 문제 해결~!

 

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(input().strip()) for _ in range(m)]
visited = [[False] * n for _ in range(m)]
our = []
enemy = []
steps = [(0, 1), (1, 0), (-1, 0), (0, -1)]

for i in range(m):
    for j in range(n):
        if not visited[i][j]:
            q = deque()
            q.append((i, j))
            visited[i][j] = True
            temp = 1
            while q:
                x, y = q.popleft()
                for step in steps:
                    next_x, next_y = x + step[0], y + step[1]
                    if 0 <= next_x < m and 0 <= next_y < n and not visited[next_x][next_y] and arr[next_x][next_y] == arr[x][y]:
                        visited[next_x][next_y] = True
                        temp += 1
                        q.append((next_x, next_y))
            our.append(temp ** 2) if arr[i][j] == 'W' else enemy.append(temp ** 2)

print(sum(our), sum(enemy))