[boj] 백준 1303 전쟁 - 전투 python 풀이

bfs로 풀이함

 

문제

 

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

1303번: 전쟁 - 전투

 

코드

 

import sys
input = sys.stdin.readline
import collections

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

move = {(-1,0),(0,1),(1,0),(0,-1)}

def bfs(x,y,MAP,color):
    q = collections.deque()
    q.append((x,y))
    MAP[x][y] = 'Z'
    cnt = 1

    while q:
        x,y = q.popleft()

        for tx,ty in move:
            nx = tx + x
            ny = ty + y

            if 0<=nx<M and 0<=ny<N and MAP[nx][ny] != 'Z' and MAP[nx][ny] == color:
                q.append((nx,ny))
                MAP[nx][ny] = 'Z' #visited
                cnt += 1

    return cnt

Blue, White = 0, 0
for i in range(M):
    for j in range(N):
        if MAP[i][j] == 'W':
            White += bfs(i,j,MAP,'W')**2
        elif MAP[i][j] == 'B':
            Blue += bfs(i,j,MAP,'B')**2
        
print(White, Blue)