[백준] 1303 전쟁 - python

• 문제 링크 : https://www.acmicpc.net/problem/1303
• 접근 방법 : 인접한 병사들의 수를 세는 것이 목적이다. 현재 위치에서 모든 노드를 탐색할 필요없이 인접한 우리 병사의 수만 세면 되므로 BFS를 사용하였다.

from collections import deque

m, n = map(int, input().split())
graph = [list(input()) for _ in range(n)]

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

visited = [[0]*m for _ in range(n)]

q = deque()

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

    while q:
        x, y = q.popleft()
        
        # 상하좌우에 있는 병사가 아군인지 확인
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0<=nx<n and 0<=ny<m and visited[nx][ny]==0 and graph[x][y] == graph[nx][ny]:
                q.append((nx,ny))
                visited[nx][ny] = 1
                cnt += 1
    return cnt

for a in range(n):
    for b in range(m):
        if visited[a][b] == 0:
            answer = bfs(a,b)
            if graph[a][b] == 'W': W += answer ** 2
            else: B += answer ** 2

print(W,B)