[백준] 1743 : 음식물 피하기 python

 

NxM 크기의 그래프를 만들고 음식물쓰레기가 있는 자리는 1로 표시한다.

그리고 그래프에서 아직 미방문이면서 음식물쓰레기가 있는 자리에서부터 BFS나 DFS를 수행하면서 쓰레기의 크기를 cnt_list에 추가해줬다.

모든 탐색이 끝나고나서 max(cnt_list)를 출력해주면 된다.

 

from collections import deque
import sys
input = sys.stdin.readline

def bfs(a,b):
    q = deque()
    q.append((a,b))
    visited[a][b] = 1
    cnt = 1
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            # 미방문이면서 음식물쓰레기가 있는 자리라면 큐에 넣고 cnt를 증가시킴
            if 0<=nx<N and 0<=ny<M and visited[nx][ny]==0 and graph[nx][ny]==1:
                q.append((nx,ny))
                visited[nx][ny]=1
                cnt +=1
    return cnt

N,M,K = map(int,input().split())
    
graph = [[0 for j in range(M)]for i in range(N)]
visited = [[0 for j in range(M)]for i in range(N)]
cnt_list = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for i in range(K):
    x,y = map(int,input().split())
    graph[x-1][y-1] = 1

for i in range(N):
    for j in range(M):
        if visited[i][j]==0 and graph[i][j]==1:
            cnt_list.append(bfs(i,j))
print(max(cnt_list))