1743 음식물 피하기 bfs

ylab 2023. 2. 27. 18:25

https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다

www.acmicpc.net

from collections import deque

n,m,k = map(int,input().split())
#그래프 표기
graph = [[0]*m for _ in range(n)]
#그래프에 칸 채우기
for _ in range(k):
    r,c = map(int,input().split())
    graph[r-1][c-1]=1
#print(graph)

#하 상 좌 우            
dx=[-1,1,0,0]
dy=[0,0,-1,1]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0
    trash = 1
    
    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:
                graph[nx][ny] =0
                queue.append((nx,ny))
                trash+=1
    result.append(trash)
    
result = []

for i in range(n):
    for j in range(m):
        if graph[i][j]==1:
            bfs(i,j)

#오름차순 정렬
result.sort()
print(result[-1])