[백준] 1926 "그림" -python

 

알고리즘

 BFS를 통해 그래프를 탐색하면서 시작지점의 개수와 bfs를 통해 방문한 개수를 각각 저장하여 출력한다.

 

소스코드

# 그림
import sys

n, m = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

cnt = 0
result = 0
visited = [[0 for i in range(m)] for j in range(n)]
q = []
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

for i in range(n):
    for j in range(m):
        if visited[i][j] or arr[i][j] == 0:
            continue
        cnt += 1
        visited[i][j] = 1
        q.append([i,j])
        mx  = 0
        while q:
            mx += 1
            cx, cy = q.pop()            
            for k in range(4):
                nx, ny = cx+dx[k], cy+dy[k]
                if not (0<=nx<n and 0<=ny<m):
                    continue
                if visited[nx][ny] or arr[nx][ny] == 0:
                    continue
                visited[nx][ny] = 1
                q.append([nx, ny])            
        
        result = max(mx, result)
        
print(cnt, result)

 

참고 : https://blog.encrypted.gg/941