[SWEA] 14195. 미생물 관찰 (Python)

link 🔗 https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AX_Pn1I6fBQDFARi 

SW Expert Academy

 

1️⃣ BFS 사용

2️⃣ for문 → A나 B 발견 → BFS 돌리기

3️⃣ BFS 끝나면 Max와 개체의 크기 비교 → Max 갱신

 

from collections import deque

def bfs(y, x):
    global Max
    q = deque()
    q.append((y, x)) # y, x, 크기
    char = arr[y][x]
    cnt = 1
    while q:
        nowy, nowx = q.popleft()
        directy = [-1, 1, 0, 0]
        directx = [0, 0, -1, 1]
        for i in range(4):
            dy = directy[i]+nowy
            dx = directx[i]+nowx
            if 0 <= dy < n and 0 <= dx < m:
                if visit[dy][dx] == 0 and arr[dy][dx] == char:
                    visit[dy][dx] = 1
                    cnt += 1
                    q.append((dy, dx))
    if Max < cnt:
        Max = cnt

t = int(input())
for tc in range(1, t+1):
    n, m = map(int, input().split()) # y x
    arr = [list(input()) for _ in range(n)]
    visit = [[0]*m for _ in range(n)]
    A_cnt = 0
    B_cnt = 0
    Max = -1e8
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 'A' or arr[i][j] == 'B':
                if visit[i][j] == 1:continue
                visit[i][j] = 1
                if arr[i][j] == 'A':
                    A_cnt += 1
                else:
                    B_cnt += 1
                bfs(i, j)
    print(f'#{tc} {A_cnt} {B_cnt} {Max}')