swea.14195 미생물 관찰

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

SW Expert Academy

from collections import deque
T = int(input())
for tc in range(1,T+1):
    N,M = map(int,input().split())
    arr=[list(input()) for _ in range(N)]
    a_visit = [[0]*M for _ in range(N)]
    b_visit = [[0]*M for _ in range(N)]
    a_cnt,b_cnt=0,0
    a_max,b_max=0,0
    
    def a_bfs(y,x):
        global a_max
        q = deque()
        q.append((y,x))
        cnt=1
        while q:
            ny,nx = q.popleft()
            directy=[-1,1,0,0]
            directx=[0,0,-1,1]

            for i in range(4):
                dy=directy[i]+ny
                dx=directx[i]+nx

                if 0<=dy<N and 0<=dx<M:
                    if arr[dy][dx]!='A': continue
                    if a_visit[dy][dx]!=0:continue
                    a_visit[dy][dx]=1
                    cnt+=1
                    q.append((dy,dx))
        if a_max<cnt:
            a_max=cnt

    def b_bfs(y,x):
        global b_max
        q = deque()
        q.append((y,x))

        cnt=1
        while q:
            ny,nx = q.popleft()
            directy=[-1,1,0,0]
            directx=[0,0,-1,1]

            for i in range(4):
                dy=directy[i]+ny
                dx=directx[i]+nx

                if 0<=dy<N and 0<=dx<M:
                    if arr[dy][dx]!='B': continue
                    if b_visit[dy][dx]!=0:continue
                    b_visit[dy][dx]=1
                    cnt+=1
                    q.append((dy,dx))
        if b_max<cnt:
            b_max=cnt

    for i in range(N):
        for j in range(M):
            if arr[i][j] == 'A' and a_visit[i][j] == 0:
                a_cnt+=1
                a_visit[i][j]=1
                a_bfs(i,j)
            if arr[i][j] == 'B' and b_visit[i][j]==0:
                b_cnt+=1
                b_visit[i][j]=1
                b_bfs(i,j)

    answer=max(a_max,b_max)
    print(f'#{tc} {a_cnt} {b_cnt} {answer}')

전략

'A'를 발견했을 때 방문하지 않은 곳이라면 BFS를 돌려주는 것이다.

이 때 a_cnt+1은 개체의 수를 의미한다.

BFS를 타면서 cnt해주는 것은 개체의 크기를 세는 것으로 max값을 갱신해 최대 크기를 구해주었다.

'B'를 발견했을 때도 같은 방법으로 값을 구해준다.

출력에서는 a의 개체수와 b의 개체수 그리고 가장 큰 개체의 크기를 출력해야하는데, max함수를 이용해 a의 최대 크기와 b의 최대 크기를 비교해 answer로 출력해 주었다.

---

원래 하나의 bfs로 돌릴 수 있는데 그냥 나는 a찾기와 b찾기를 따로 함수를 만들어 돌렸다.

더 줄이면 줄일 수 있겠지만 내가 헷갈려서...

그냥 따로 만들어 주었는데 하나로 돌리는거와 시간상 차이는 없어보인다.