[Baekjoon] 1926. 그림 - python

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

1926번: 그림

문제 정보

문제 유형	난이도	걸린 시간	해결 유무	스스로 구현 성공
BFS	실버1	45m	O	O

설계 방법

BFS

코드

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

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

arr = []
visited = [[0]*m for _ in range(n)]

dx = [1,0,-1,0]
dy = [0,1,0,-1]

def bfs(i,j):
    q = deque()
    q.append((i,j))
    visited[i][j] = 1
    cnt = 0
    while q:
        x, y = q.popleft()
        # q에서 popleft할 때마다 cnt하면, 넓이 구할 수 있음 
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (nx < 0 or nx >= n or ny<0 or ny >= m): continue
            if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                visited[nx][ny] = 1
                q.append((nx, ny))
    return cnt

for i in range(n):
    for j in range(m):
        # graph[i][j] == 1 이면서, 방문하지 않은 칸에서만 bfs 실행
        if graph[i][j] == 1 and visited[i][j] == 0:
            arr.append(bfs(i,j))

print(len(arr))
# len(arr) == 0이면 "ValueError: max() arg is an empty sequence" 발생
if len(arr) == 0:
    print(0)
else:
    print(max(arr))

시간 복잡도

O(N)

어려웠던 점

1. https://www.acmicpc.net/problem/2178 이 문제와 같이 최단 경로를 구하는 문제에서는 graph[nx][ny] = graph[x][y] + 1해주면 되는데 넓이를 구할 때는 q에서 pop을 한 만큼 더해주어야 함
2. len(arr) == 0이면 max(arr)시 "ValueError: max() arg is an empty sequence" 발생