[Algorithm][bfs] 백준-1926

 

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

---

 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
arr = [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]

def bfs(y, x): # bfs 구현 암기
    rs = 1
    q = [(y,x)]
    while q:
        ey, ex = q.pop()
        for k in range(4):
            ny = ey + dy[k]
            nx = ex + dx[k]
            if 0<=ny<n and 0<=nx<m and arr[ny][nx]==1 and chk[ny][nx]==False:
                    rs += 1
                    chk[ny][nx] = True
                    q.append((ny, nx))
    return rs

maxv = 0
cnt = 0
for j in range(n):
    for i in range(m):
        if arr[j][i] == 1 and chk[j][i] == False:
            cnt += 1
            chk[j][i] = True
            maxv = max(maxv, bfs(j,i))

print(cnt)
print(maxv)

 

 

---

 

참고 - 유튜브 선생님 :) 

https://www.youtube.com/watch?v=ansd5B27uJM&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=2