[백준] 1303번 > 전쟁 - 전투

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

1303번: 전쟁 - 전투

문제

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

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

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

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

입력

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

출력

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

 

---

풀이

 

전형적인 DFS/BFS 문제이다. 나는 deque를 사용한 BFS로 문제를 해결하였다.

문제의 핵심은 뭉쳐있는 덩어리의 수를 파악하는 것이다.

 

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

n, m = map(int, input().split())
my_power = 0
enemy_power = 0
graph = [list(input().strip()) for _ in range(m)] # 상하좌우만 검사해서 뭉쳐있는 덩어리 제곱
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
team = ''

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    team = graph[x][y]
    count = 1
    graph[x][y] = '.'
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == team:
                count += 1
                graph[nx][ny] = '.'
                queue.append((nx, ny))
    return (count, team)

for i in range(m):
    for j in range(n):
        if graph[i][j] == 'W' or graph[i][j] == 'B':
            count,team = bfs(i, j)
            if team == 'W':
                my_power += count**2
            else:
                enemy_power += count **2

print(my_power, enemy_power)