알고리즘/[python] 백준 BOJ
python] 백준 1743 음식물 피하기
Alan_Kim
2024. 6. 14. 09:01
728x90
반응형
https://www.acmicpc.net/problem/1743

문제 해결
일반적인 bfs문제;
CODE
import sys
input = sys.stdin.readline
from collections import deque
def bfs(x,y):
que = deque()
dxs = [-1, 1, 0, 0]
dys = [0, 0, -1, 1]
que.append((x,y))
visited[x][y] = 1
result = 1
while que:
a, b = que.popleft()
for dx, dy in zip(dxs, dys):
na = a + dx; nb = b + dy
if 0<na<=n and 0<nb<=m and visited[na][nb] == 0 and graph[na][nb] == 1:
visited[na][nb] = 1
result += 1
que.append((na,nb))
return result
if __name__ == "__main__":
n, m, k = map(int, input().split())
graph = [[0 for _ in range(m+1)] for _ in range(n+1)]
visited = [[0 for _ in range(m+1)] for _ in range(n+1)]
for _ in range(k):
r, c = map(int, input().split())
graph[r][c] = 1
ans = 0
for i in range(1,n+1):
for j in range(1,m+1):
if graph[i][j] == 1 and visited[i][j] == 0:
res = bfs(i,j)
ans = max(ans, res)
print(ans)
728x90
반응형