백준 1743번 음식물 피하기 | python | bfs

문제

링크

풀이

백준 전투 문제와 비슷하며 난이도는 더 쉽다.

bfs()를 이용해 음식물 그룹을 파악함과 동시에 음식물 개수를 반환한다.

따라서 모든 위치에 대하여 bfs()를 수행하였을 때 반환되는 음식물 개수의 최댓값을 최종 결과값으로 지정하여 출력하면 된다.

매우 쉬우므로 해설은 여기서 끝 !

from collections import deque
import sys

input = sys.stdin.readline

n, m, k = map(int, input().strip().split())
arr = [[0] * m for _ in range(n)]

for _ in range(k):
    r, c = map(int, input().strip().split())
    arr[r - 1][c - 1] = 1


d = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def bfs(y, x):
    q = deque()
    q.append((y, x))
    arr[y][x] = 0  # 쓰레기 치웠다는 의미 (=방문했다는 의미)
    cnt = 0
    while q:
        y, x = q.popleft()
        cnt += 1
        for dy, dx in d:
            Y, X = y + dy, x + dx
            if (0 <= Y < n) and (0 <= X < m) and arr[Y][X] == 1:
                arr[Y][X] = 0
                q.append((Y, X))

    return cnt


result = 1
for y in range(n):
    for x in range(m):
        if arr[y][x] == 1:
            # print(bfs(y, x))
            result = max(result, bfs(y, x))

print(result)