음식물 피하기(1743 백준)

파이썬 deque를 사용해서 bfs를 수행한다. 

import sys 
from collections import deque  
input = sys.stdin.readline 
n,m,k  = map(int, input().split())
gra = [[0 for _ in range(m)]for _ in range(n)]
for i in range(k):
    a,b = map(int, input().split())
    gra[a-1][b-1] = 1 
# print(gra)
visited = [[0 for _ in range(m)]for _ in range(n)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def bfs(x,y) :
    q = deque([])
    q.append((x,y))
    ans = 0
    visited[x][y] = 1 
    while q :
        x,y = q.popleft()
        
        ans += 1 
        for i in range(4) :
            nx,ny = x+dx[i],y+dy[i] 
            if ( 0<=nx<n and 0<=ny<m and gra[nx][ny] == 1 ):
                if visited[nx][ny] == 0 :
                    q.append((nx,ny))
                    visited[nx][ny]= 1
                    
    return ans             
    
maxnum =0 
for i in range(n):
    for j in range(m):
        if gra[i][j] == 1 : 
            # 음식물 있으니 bfs 하기 
            maxnum = max(bfs(i,j),maxnum) 
print(maxnum)