1303(전쟁 - 전투) - 해결

전쟁 - 전투

 

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.

그러나 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.

문제는, 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

 

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. (B는 파랑, W는 흰색이다.)

 

출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

---

2개의 색을 보고 연결 되어있는 것을 파악하면 되니깐 

브루트포스하게 모든 구역을 확인하면서 bfs로 몇개가 연결되어있는지 확인하는 방식을 사용하고자 하였다.

그래서 연결되어있는 수 만큼 카운트하여 bfs가 끝난 뒤 제곱을 하여 더하는 방식을 사용하였다.

 

import sys
input = sys.stdin.readline

N, M = map(int,input().split())

num_list = [list(input()) for _ in range(M)]

dirs = [(-1,0),(0,1),(1,0),(0,-1)]

# 위치, 색깔
def bfs(x,y,C):
    global cnt_W, cnt_B

    q = [(x,y,C)]
    # 다른 아무 문자로 visit 역할을 대신
    num_list[x][y] = "A"

    # 카운트는 현재부터 시작하기 때문에 1로 시작
    cnt = 1

    # bfs 시작
    while q:
        i,j,C = q.pop(0)
        # 탐색
        for dir in dirs:
            ni = i + dir[0]
            nj = j + dir[1]
            # 범위안에서 같은 색이면
            if 0<= ni < M and 0 <= nj < N and num_list[ni][nj] == C:
                q.append((ni,nj,C))
                num_list[ni][nj] = "A"
                # 연결된 병사 증가
                cnt += 1
    # 그 색에 카운트를 제곱해서 증가
    if C == "W":
        cnt_W += cnt ** 2
    else:
        cnt_B += cnt ** 2


cnt_W = 0
cnt_B = 0
# 모든 곳을 탐색
for i in range(M):
    for j in range(N):
        # 그 색에 맞게 bfs
        if num_list[i][j] == "W":
            bfs(i,j,"W")
        elif num_list[i][j] == "B":
            bfs(i,j,"B")

print(cnt_W,cnt_B)