[알고리즘/백준] 1926번 : 그림(python)

간단한 dfs, bfs 문제이다.

위에가 bfs 밑에가 dfs 이다.

dfs

def dfs(x, y):
    a[x][y] = 0
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    w = 1
    q = list()
    q.append([x, y])
    while q:
        x, y = q.pop()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < n and 0 <= ny < m and a[nx][ny] == 1:
                    q.append([nx, ny])
                    a[nx][ny] = 0
                    w += 1
    return w


n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
ans = 0
for i in range(n):
    for j in range(m):
        if a[i][j] == 1:
            cnt += 1
            ans = max(dfs(i, j), ans)

print(cnt)
print(ans)

bfs

from collections import deque

def bfs(x, y):
    a[x][y] = 0
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    w = 1
    q = deque()
    q.append([x, y])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < n and 0 <= ny < m and a[nx][ny] == 1:
                q.append([nx, ny])
                a[nx][ny] = 0
                w += 1
    return w


n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
ans = 0
for i in range(n):
    for j in range(m):
        if a[i][j] == 1:
            cnt += 1
            ans = max(bfs(i, j), ans)

print(cnt)
print(ans)