[백준] 1926번 그림 파이썬 python

문제

이 문제는 딱 봐도 DFS/BFS 문제다.

그래서 생각한 것은 이중 for 문을 돌면서 1을 만나면 해당 좌표와 연결된 1 부분을 모두 계산한 후 방문처리 해주는 것을 반복해주기로 했다.

해당 좌표와 연결된 1의 좌표를 구하는 함수를 bfs 로 두고 bfs 호출할 때마다 ans1에 +1 해주어 그림의 개수를 구해주었다.

코드

from collections import deque
n,m = map(int, input().split())
paint = []
for _ in range(n):
    paint.append(list(map(int, input().split())))

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

def bfs (x,y):
    q =deque()
    q.append((x,y))
    dx= [-1,1,0,0]
    dy = [0,0,1,-1]
    visited[x][y] = 1
    cnt = 1
    while(q):
        x,y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            #방문한적 없고 현재x,y와 이어진 즉, 같은 그림인 칸의 개수 세기
            if 0<= nx <n and 0<= ny <m and visited[nx][ny] == 0 and paint[nx][ny] == 1:
                visited[nx][ny] = 1
                q.append((nx,ny))
                cnt+=1
    return cnt


ans1 = 0
ans2 = 0
for i in range(n):
    for j in range(m):
        if paint[i][j] == 1 and visited[i][j] == 0:
            ans1+=1
            ans2 = max(ans2, bfs(i,j))

print(ans1)
print(ans2)

문제 내용만 달랐지 유사한 문제가 너무 많아서 쉽게 해결했던 것 같다.