BOJ 1303 - 전쟁 - 전투

문제

백준 온라인 저지 - 1303번

풀이 과정

두 세력간의 규모를 측정하는 BFS 문제입니다.
W 와 B 로 나누어진 컴포넌트의 크기를 구하면 되는데 이때 BFS 를 활용하고
각 컴포넌트의 크기를 구할때마다 제곱한 값을 세력 규모에 더해주면 됩니다.

코드

import sys
from collections import deque

N, M = list(map(int, sys.stdin.readline().split()))
board = [list(sys.stdin.readline().strip()) for _ in range(M)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def in_range(x, y):
    return 0 <= x < M and 0 <= y < N


def bfs(x, y, visit):
    q = deque()
    check = 0

    q.append([x, y])
    visit[x][y] = 1

    while q:
        x, y = q.popleft()
        check += 1

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if in_range(nx, ny) and board[nx][ny] == board[x][y] and not visit[nx][ny]:
                q.append([nx, ny])
                visit[nx][ny] = 1

    return check


def solution():
    warrior = {
        'B': [],
        'W': []
    }
    visit = [[0] * N for _ in range(M)]

    for x in range(M):
        for y in range(N):
            if not visit[x][y]:
                size = bfs(x, y, visit)
                warrior[board[x][y]].append(size)

    W = sum(map(lambda x: x**2, warrior['W']))
    B = sum(map(lambda x: x**2, warrior['B']))

    return f"{W} {B}"


print(solution())