Baekjoon 1926번 그림

💭 문제가 궁금하다면?

내가 시도한 방법

• 그림 탐색 방법으로 BFS 활용
  • 그림의 넓이를 BFS 반환값으로 하여 최대일 때 갱신되도록 함
  • 가로 또는 세로 방향으로 연결된 그림인지 파악하면서, 1인 경우 0으로 갱신하여 중복 방문 방지

def BFS(i, j):
    q = [(i, j)]
    paper[i][j] = 0

    width = 1

    while q:
        ci, cj = q.pop(0)

        for di, dj in (0, 1), (0, -1), (1, 0), (-1, 0):
            ni, nj = ci + di, cj + dj
            
            if 0 <= ni < N and 0 <= nj < M and paper[ni][nj]:
                q.append((ni, nj))
                paper[ni][nj] = 0
                width += 1

    return width


# 입력 받기
N, M = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(N)]

# 출력 변수
count_picture = width_picture = 0

# 그림 파악하기
for i in range(N):
    for j in range(M):
        if paper[i][j]:
            width_picture = max(BFS(i, j), width_picture)
            count_picture += 1

# 출력 하기
print(count_picture)
print(width_picture)