[백준 1303번] 파이썬 - 전투

백준 1303_전투

조건

• 전쟁은 어느덧 전면전이 시작되었다.
• 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.
• 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.
• 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.
• N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다.
• 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

접근 방법

• visited 배열을 만들어주고 방문하지 않은 경우에만 bfs를 돌려준다.
• bfs를 돌리며 cnt를 기록해주고 각 진영에 CNT의 제곱만큼 결과를 더해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

di, dj = [1,-1,0,0], [0,0,1,-1]  
def bfs(color, si, sj):  
    global val_w, val_b  
    q = deque()  
    q.append((si, sj))  
    visited[si][sj] = 1  
    cnt = 0  
    while q:  
        cnt += 1  
        x, y = q.popleft()  

        for i in range(4):  
            ni, nj = x+di[i], y+dj[i]  
            if 0 <= ni < M and 0 <= nj < N and visited[ni][nj] == 0 and arr[ni][nj] == color:  
                q.append((ni, nj))  
                visited[ni][nj] = 1  
    if color == 'W':  
        val_w += cnt ** 2  
    else:  
        val_b += cnt ** 2  

N, M = map(int, input().split())  
arr = [list(input().rstrip()) for _ in range(M)]  

visited=[[0]*N for _ in range(M)]  
val_w = 0  
val_b = 0  

for i in range(M):  
    for j in range(N):  
        if not visited[i][j]:  
            bfs(arr[i][j], i, j)  

print(val_w, val_b)