[백준] 그림 1926

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

# 아이디어  
# BFS 문제이긴 한대 이중 for 문 돌려서 진행  
# 시간 복잡도  
# O(V+E)  
# V : 500  
# E : V\*4 -4 = V4   
# O = 5V = 1250000 < 2초 내  
# 자료구조  

import sys  
input = sys.stdin.readline  

n, m = map(int, input().split())  
graph = \[list(map(int, input().split())) for \_ in range(n)\]  
chk = \[\[False\]\* m for \_ in range(n)\]  

# 상하좌우 4방향 이동  
dy = \[0,1,0,-1\]  
dx = \[1,0,-1,0\]  
# 헷갈렸던게 수학 좌표계가 아니고 배열 좌표계를 쓴다  
# 배열(행렬) 좌표계 (코드에서 사용)  
# (0,0)------→ x축(열)  
#  |  
#  |  \[0\]\[1\]\[2\]  
#  |  \[3\]\[4\]\[5\]  
#  |  \[6\]\[7\]\[8\]  
#  ↓  
# y축(행)  

def bfs(y, x):  
    rs = 1 # 현재 위치도 그림의 일부이기에 (자기 자신 포함)  

    q = \[(y,x)\]  
    while q:  
        cur\_y, cur\_x = q.pop()  
        for k in range(4):  
            next\_y = cur\_y + dy\[k\]  
            next\_x = cur\_x + dx\[k\]  
            # 사이즈가 넘어가면 안되기에  
            if 0 <= next\_y < n and 0 <= next\_x < m:  
                if graph\[next\_y\]\[next\_x\] == 1 and chk\[next\_y\]\[next\_x\] == False:  
                    chk\[next\_y\]\[next\_x\] = True  
                    rs += 1  
                    q.append((next\_y, next\_x))  
    return rs  

cnt = 0  
max\_val = 0  

# 이중 for 문으로 검사  
for j in range(n):  
    for i in range(m):  
        if graph\[j\]\[i\] == 1 and chk\[j\]\[i\] == False:  
            chk\[j\]\[i\] = True  
            cnt += 1  
            max\_val = max(max\_val, bfs(j,i))  


print(cnt)  
print(max\_val)