240528 [BOJ/백준] 1926. 그림

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

---

나의 코드

n, m = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]
q = []

ans = 0
max_v = 0
for i in range(n):
    for j in range(m):
        if paper[i][j] and not visited[i][j]:
            q.append([i, j])
            visited[i][j] = 1
            S = 1  # 가장 넓은 그림의 넓이를 위한 최솟값 설정
            while q:
                x, y = q.pop(0)
                for k in range(4):
                    ni = x + di[k]
                    nj = y + dj[k]
                    if 0 <= ni < n and 0 <= nj < m and not visited[ni][nj] and paper[ni][nj]:
                        visited[ni][nj] = 1
                        q.append([ni, nj])
                        S += 1
            ans += 1
            max_v = max(max_v, S)

print(ans)
print(max_v)

결과

---

내가 좋아하는 유형의 문제 중에 하나! 이제 BFS랑 DP는 자신있게 풀 수 있을 것 같다. 평소에 풀던 BFS랑 다를 게 없어서 설명에 쓸 것도 없다. 간만에 알고리즘 문제풀이 폭주하는중!ㅎㅎ