[ BOJ / 파이썬] 1926 그림

/  제출 1  /

from collections import deque
#세로, 가로
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
visited = [[False]*m for _ in range(n)]
q = deque([])
def bfs():
  cnt = 0
  while q:
    cnt += 1
    x, y = q.pop()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      
      if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == False and board[nx][ny] == 1:
        visited[nx][ny] = True
        q.append((nx, ny))
  return cnt
  
maxArea = 0
count = 0
for x in range(n):
  for y in range(m):
    if board[x][y] == 1 and visited[x][y] == False:
      thisArea = 0
      count += 1
      visited[x][y] = True
      q.append((x, y))
      thisArea = bfs()
      maxArea = max(maxArea, thisArea)
print(count)
print(maxArea)

 

 

정석적인 BFS문제입니다.

BFS알고리즘을 이해하면 잘 구현할 수 있는 문제입니다.
해당 알고리즘을 제대로 이해해서 응용을 잘 할 수 있도록 계속 연습하겠습니다.