백준 1926. 그림

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

1926번: 그림

'''
그림의 개수와 최대 그림 넓이 출력
'''

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
di = [-1,1,0,0]
dj = [0,0,-1,1]
cnt = 0
max_area = 0
def bfs(si,sj):
    global max_area
    q = deque([(si,sj)])
    visited[si][sj] = 1
    area = 1
    while q:
        i,j = q.popleft()
        for w in range(4):
            ni, nj = i+di[w], j+dj[w]
            if 0<=ni<n and 0<=nj<m and visited[ni][nj] == 0:
                if arr[ni][nj] == 1:
                    q.append((ni,nj))
                    visited[ni][nj] = visited[i][j] + 1
                    area += 1
    max_area = max(max_area, area)
for k in range(n):
    for h in range(m):
        if arr[k][h] == 1 and visited[k][h] == 0:
            cnt += 1
            bfs(k,h)

print(cnt)
print(max_area)

 

여기서 처음에 max_area 부분만 틀렸었는데 그 이유가 bfs를 돌릴 때마다 area를 새로 재야됐어야 했는데 그러지 않아서였다...

def bfs(si,sj):
    global max_area
    q = deque([(si,sj)])
    visited[si][sj] = 1
    while q:
        i,j = q.popleft()
        for w in range(4):
            ni, nj = i+di[w], j+dj[w]
            if 0<=ni<n and 0<=nj<m and visited[ni][nj] == 0:
                if arr[ni][nj] == 1:
                    q.append((ni,nj))
                    visited[ni][nj] = visited[i][j] + 1
                    if max_area <= visited[ni][nj]:
                        max_area = visited[ni][nj]
for k in range(n):
    for h in range(m):
        if arr[k][h] == 1 and visited[k][h] == 0:
            cnt += 1
            bfs(k,h)

print(cnt)
print(max_area)

 

영역의 크기(bfs 한번 돌릴때의 모든 1의 개수)와 처음부터 가장 멀리 갔을 때의 노드의 거리랑 헷갈리지 말자!