[baekjoon] 1926 그림 실버1

백준 DFS/BFS 문제
링크 : https://www.acmicpc.net/problem/1926

설명

• BFS로 해결하는 간단한 문제이다.

---

코드

from collections import deque

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

arr = [list(map(int,input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
cnt = 0
ans = 0
dx=[1,-1,0,0]
dy = [0,0,1,-1]
def BFS(x,y):
    q = deque()
    q.append([x,y])
    visited[x][y] = 1
    temp = 1
    while q:
        x,y = q.popleft()
        
        for i in range(4):
            nx,ny = x + dx[i], y+dy[i]
            if 0<= nx < n and 0<= ny < m and visited[nx][ny] == 0:
                if arr[nx][ny] == 1:
                    temp += 1
                    visited[nx][ny] =1
                    q.append([nx,ny])
    
    return temp

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and visited[i][j] == 0:
            ans = max(ans,BFS(i,j))
            cnt+= 1

print(cnt)
print(ans)

생각한 점

• visited 배열을 추가로 사용하여 이미 크기를 구한 곳은 다시 구하지 못하게 하였다.
• 다른 코드를 보니 추가적인 배열을 사용하지 않고, arr[nx][ny] = 0으로 바꿔주며 이미 한번 지나간 곳은 다시 하지 않도록 설계하였다.