백준 1303번 전쟁 - 전투

문제:
전쟁이 일어난 땅에는 두 나라가 존재한다. 각각 W, B로 표현되며, 같은 병사끼리 인접한(상하좌우) 곳에 모이면 하나의 군대를 형성한다. 각 나라의 전투력은 군대에 속한 병사의 수의 제곱으로 정의된다. 지도를 보고 양 나라의 전투력을 계산하시오.
입력
첫 줄에 가로 크기 W와 세로 크기 H가 주어진다. 그 다음 H줄에 W개의 문자가 입력된다. 문자는 W 또는 B 중 하나이다.
출력
첫째 줄에 우리 병사의 전투력과 적국 병사의 전투력을 출력한다.

from collections import deque

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

w,h = map(int, input().split())
graph = [list(map(str,input().strip())) for _ in range(h)]
visited = [[False]*w for _ in range(h)]
ours = []
yours = []

def bfs1(x,y):
    q = deque()
    q.append((x,y))
    visited[y][x] = True
    our = 1

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0<=nx<w and 0<=ny<h and not visited[ny][nx] and graph[ny][nx] == 'W':
                our+=1
                visited[ny][nx] = True
                q.append((nx,ny))

    return our

def bfs2(x,y):
    q = deque()
    q.append((x,y))
    visited[y][x] = True
    you = 1

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0<=nx<w and 0<=ny<h and not visited[ny][nx] and graph[ny][nx] == 'B':
                you+=1
                visited[ny][nx] = True
                q.append((nx,ny))

    return you

for y in range(h):
    for x in range(w):
        if graph[y][x] == 'W' and not visited[y][x]:
            ours.append(bfs1(x,y))
        if graph[y][x] == 'B' and not visited[y][x]:
            yours.append(bfs2(x,y))

print(sum(i*i for i in ours), sum(i*i for i in yours))
  

맨 위로 이동