[๋ฐฑ์ค-1926] ๊ทธ๋ฆผ / Python
๐ Problem Solving/Baekjoon
1926๋ฒ: ๊ทธ๋ฆผ
์ด๋ค ํฐ ๋ํ์ง์ ๊ทธ๋ฆผ์ด ๊ทธ๋ ค์ ธ ์์ ๋, ๊ทธ ๊ทธ๋ฆผ์ ๊ฐ์์, ๊ทธ ๊ทธ๋ฆผ ์ค ๋์ด๊ฐ ๊ฐ์ฅ ๋์ ๊ฒ์ ๋์ด๋ฅผ ์ถ๋ ฅํ์ฌ๋ผ. ๋จ, ๊ทธ๋ฆผ์ด๋ผ๋ ๊ฒ์ 1๋ก ์ฐ๊ฒฐ๋ ๊ฒ์ ํ ๊ทธ๋ฆผ์ด๋ผ๊ณ ์ ์ํ์. ๊ฐ๋ก๋ ์ธ๋ก
www.acmicpc.net
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
size = 0
answer_size = 0
cnt = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
global size, answer_size
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
size += 1
graph[nx][ny] = 0
queue.append((nx, ny))
answer_size = max(size, answer_size)
size = 0
for i in range(n):
for j in range(m):
if graph[i][j] == 1:
graph[i][j] = 0
size = 1
cnt += 1
bfs(i, j)
print(cnt)
print(answer_size)
ํด์ค
bfs๋ก ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ์๋ค.
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-6118] ์จ๋ฐ๊ผญ์ง / Python (0) | 2021.07.02 |
---|---|
[๋ฐฑ์ค-1743] ์์๋ฌผ ํผํ๊ธฐ / Python (0) | 2021.07.02 |
[๋ฐฑ์ค-2251] ๋ฌผํต / Python (0) | 2021.07.01 |
[๋ฐฑ์ค-17413] ๋จ์ด ๋ค์ง๊ธฐ 2 / Python (1) | 2021.06.28 |
[๋ฐฑ์ค-1138] ํ ์ค๋ก ์๊ธฐ / Python (0) | 2021.06.21 |