[BOJ][⚪1][백준#01303] 전쟁 - 전투

문제 출처

BAEKJOON Online Judge #1303

문제

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

입력

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

출력

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

예제

입력

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

출력

130 65

My Sol

import sys
input = sys.stdin.readline
from collections import deque

def bfs(ni, nj, nc):
    global mat, wCnt, bCnt
    cnt = 0
    Q = deque()
    Q.append((ni, nj))

    while Q:
        ni, nj = Q.popleft()
        if not mat[ni][nj]: continue
        mat[ni][nj] = ''
        cnt += 1
        for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
            si, sj = ni+di, nj+dj
            if not (0<=si<I and 0<=sj<J): continue
            if not mat[si][sj]==nc: continue
            Q.append((si, sj))

    if nc=='W':
        wCnt += cnt**2
    else:
        bCnt += cnt**2


J, I = map(int, input().split())
mat = [list(input()) for _ in range(I)]

wCnt = bCnt = 0
for i in range(I):
    for j in range(J):
        if mat[i][j]:
            bfs(i, j, mat[i][j])

print(wCnt, bCnt)

전형적인 BFS 문제였다. BFS를 처리한 영역은 공백으로 바꾸기 때문에 모든 좌표를 완전탐색하면서, 공백이 아닌 지점을 발견하면 해당 값을 인자로 포함한 BFS를 돌려 상하좌우로 연결된 영역을 모두 공백으로 처리하고 카운트를 세어주어 이를 제곱한 값을 전역의 변수에 더해준다.

이때 BFS로 전달해준 색깔 값을 이용하여 어떤 변수에 힘을 더해줄 것인지 판단하여 더해주고, 모든 좌표에 대해 완전탐색을 마치면 각 변수를 출력해주면 되겠다.

결과

맞았습니다!!