[Python/파이썬] 백준 1303번 전쟁 - 전투

1303번: 전쟁 - 전투

 

코드

from collections import deque

n, m = map(int, input().split())
board = [input() for _ in range(m)]
visited = [[False]*n for _ in range(m)]
power = {"W": 0, "B": 0}  # 각 나라의 병사의 위력의 합


def bfs(x, y, color):
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    q = deque([(x, y)])
    cnt = 1
    visited[x][y] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and board[nx][ny] == color:
                q.append((nx, ny))
                visited[nx][ny] = True
                cnt += 1
    return cnt


for i in range(m):
    for j in range(n):
        if not visited[i][j]:
            power[board[i][j]] += bfs(i, j, board[i][j])**2

print(*power.values())

 

아직 방문하지 않은 칸에 도착하면 해당 칸에서부터 뭉쳐있는 병사들, 즉 상하좌우로 서로 인접한 아군의 수를 BFS를 이용하여 센다. 기존의 BFS 알고리즘에 같은 색의 병사인지 확인하는 조건만 넣어주면 된다. 그리고 q에 넣을 때마다 그 칸의 병사는 같은 뭉텅이에 속해있다는 뜻이므로 cnt를 1 증가시켜준다.