[알고리즘/백준] 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)
Author And Source
이 문제에 관하여([알고리즘/백준] 1926번 : 그림(python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@y7y1h13/알고리즘백준-1926번-그림python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)