[백준/Python] 1303번 : 전쟁 - 전투

문제

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

1303번: 전쟁 - 전투

---

풀이

- deque를 이용하여 BFS로 구현하였다.
- 이중 반복문을 통해 탐색을 시작할 위치를 찾고, bfs를 호출한 결과의 제곱을 합한다.

- bfs함수가 호출이 되면, 시작 위치를 방문했으므로 0으로 변경하고 q를 생성하여 시작 좌표를 append 하고 반복문을 통해 상하좌우를 확인한다.
- 만약 상하좌우의 좌표가 범위를 벗어나지 않고 해당 위치의 병사가 시작 위치의 병사와 동일하다면, cnt 증가, 방문여부 변경, q에 좌표 append를 한다.
- q가 비었다면 반복문이 종료된 후 cnt를 반환한다.

---

코드

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(m)]

dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
def bfs(y, x, s):
    global cnt
    graph[y][x] = 0
    q = deque()
    q.append([y, x])
    while q:
        y, x = q.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < n and 0 <= ny < m and graph[ny][nx] == s:
                graph[ny][nx] = 0
                cnt += 1
                q.append([ny, nx])
    return cnt

w_total, b_total = 0, 0
for i in range(m):
    for j in range(n):
        cnt = 1
        if graph[i][j] == 'W':
            w_total += bfs(i, j, 'W')**2
        if graph[i][j] == 'B':
            b_total += bfs(i, j, 'B')**2

print(w_total, b_total)