[백준] 1926_그림 BFS 실1 (Python3)

백준 BFS 먹으러 옴

 

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

 

실1이라서 보자마자 바로 BFS가 머리에 그려지는 수준

 

이중 for문으로 이차원 배열을 탐색하다가

1을 발견하면, 그때부터 bfs를 시작한다

 

해당 시작점을 기준으로 상하좌우 노드를 탐색해서, 만약 1이라면 q에 넣어준다

q에 더 이상 탐색할 점이 남지 않을 때까지 while문을 돌린다

while문을 돌릴 때마다 그림의 크기+1을 해주고

탐색이 다 끝나면 그림 크기를 return한다

 

이거 visited로 탐색 여부 볼 수 있을까 싶어서 visited 이차원 배열을 만들어서 False로 초기화 했는데

중간에 좀 꼬여서 버렸다

 

다른 블로그 글을 찾아보니

그냥 배열을 탐색하면서 그림 크기 더해주기에 사용했으면 1을 0으로 바꿔서 visited 대신에 사용했더라

그래서 그 방법을 썼더니 풀렸다

 

그리고 시작점부터 탐색할 때, 시작점도 크기에 포함되어야 하므로 그림 크기는 1로 초기화해야 한다

 

from collections import deque

def bfs(x, y):
    q = deque()
    q.append([x,y])
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    ans = 1

    arr[x][y]=0
    while q:
        node = q.popleft()
        x0, y0 = node[0], node[1]
        for i in range(4):
            y_ = y0 + dy[i]
            x_ = x0 + dx[i]
            if 0 <= x_ < n and 0 <= y_ < m and arr[x_][y_] == 1:
                    ans += 1
                    arr[x_][y_]=0
                    q.append([x_, y_])
    maxi.append(ans)
                    

    
n,m = map(int, input().split())

arr = []
for i in range(n):
    arr.append(list(map(int,input().split())))
maxi=[0]
cnt=0
for i in range(n):
    for j in range(m):
        if arr[i][j]==1:
            bfs(i,j)
            cnt+=1

print(cnt)
print(max(maxi))