[백준/1926][Python] 그림

문제

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

1926번: 그림

풀이

이 문제도 BFS의 기본 문제.

아무래도 C++과 자바로 풀었던 문제라 쉽다고 생각했는데 vis를 Boolean으로 선언해놓고 0이냐 아니냐로 비교했더니 오류나서 한참 고생...

BFS를 함수로 선언한 코드가 많던데, 난 중복이 없길래 그냥 ... 풀어서 썼다.

이중 for문을 통해서 BFS 탐색을 시작할 위치를 고르고, 그림의 수를 카운팅해준다.

그리고 면적은 큐에 들어온 좌표 수 만큼 카운팅 해주면 된다.
max구하는 방법은 면적의 최대값을 구해야하므로, 현재 구한 면적과 이전에 구한 면적의 최대값을 비교해서 변수에 저장한다.

코드

import sys
from collections import deque

read = sys.stdin.readline
n, m = map(int, read().split())
graph = [list(map(int, read().split())) for _ in range(n)]
vis = [[False] * m for _ in range(n)]

#상하좌우
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = 0
mx = 0
for i in range(n):
  for j in range(m):
    if graph[i][j] != 0 and vis[i][j] == False:
      cnt = cnt + 1  #그림의 수 카운팅
      queue = deque()
      queue.append((i, j))
      vis[i][j] = True
      area = 0
      while queue:
        x, y = queue.popleft()
        area = area + 1  #면적 카운팅
        for dir in range(4):
          nx = x + dx[dir]
          ny = y + dy[dir]
          if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny] and graph[nx][ny] == 1:
            queue.append((nx, ny))
            vis[nx][ny] = True
      mx = max(mx, area)

print(cnt)
print(mx)