BOJ - 1743

백준 문제 링크
음식물 피하기

❓접근법

1. 이전 게시물 '그림'문제와 유사해서 BFS를 사용했다.
2. 계속 하던대로 방문한 좌표는 queue에 넣어주고,
   통로에서 변경한다.(1 -> 0)
3. 상,하,좌,우를 방문해서 1이 있는 곳을 모두 탐색한 다음 count를 return하는 함수를 만들면 된다.
4. 통로를 for문 2개로 돌면서 좌표의 값이 1이라면 count를 bfs(i,j)로 저장하고, answer에 count를 넣어준다.
5. 음식물의 최대 크기를 출력하면 된다.

👌🏻코드

from collections import deque
N,M,K = map(int,input().split())
lst = [[0] * M for _ in range(N)]

for _ in range(K):
    x,y = map(int,input().split())
    lst[x-1][y-1] = 1
    
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    
    lst[x][y] = 0
    count = 0
    
    while queue:
        x,y = queue.popleft()
        count += 1
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
        
            if (0 <= nx < N) and (0 <= ny < M) and (lst[nx][ny] == 1):
                queue.append((nx,ny))
                lst[nx][ny] = 0
                
    return count

answer = []    
for i in range(N):
    for j in range(M):
        if lst[i][j] == 1:
            count = bfs(i,j)
            answer.append(count)
            
print(max(answer))