전쟁 - 전투

백준 1303

당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력하기.

• 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.
• N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.
• 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. (B는 파랑, W는 흰색이다.)

입출력

입력	출력
5 5 WBWWW WWWWW BBBBB BBBWW WWWWW	130 65

---

접근 방식

: bfs로 상하좌우를 탐색하여 몇개가 연결되어있는지를 리턴한다.

코드

from collections import deque

n, m = map(int, input().split()) #m행n열
sol = [list(input()) for _ in range(m)]
visited = [[0]*n for _ in range(m)]


def bfs(x, y, visited, sol, v):
    q = deque()
    q.append((x, y))
    cnt = 1
    visited[x][y] = 1

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<m and 0<=ny<n:
                if visited[nx][ny] == 0 and sol[nx][ny] == v:
                    cnt += 1
                    visited[nx][ny] = 1
                    q.append((nx, ny))

    return cnt


sum_w, sum_b = 0, 0
for i in range(m):
    for j in range(n):
        if sol[i][j] == 'W' and visited[i][j] == 0:
            sum_w += pow(bfs(i,j,visited,sol,'W'), 2)
        elif sol[i][j] == 'B' and visited[i][j] == 0:
            sum_b += pow(bfs(i,j,visited,sol,'B'), 2)
print(sum_w, sum_b)

• 제곱은 pow함수를 쓰던가 **2를 사용한다.