[ 1743 ] [ BFS ] 음식물 피하기

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

1743번: 음식물 피하기

 

---

풀이 과정

---

1. 근처에 있는 음식물끼리 뭉칠수 있으므로, BFS를 진행하면 된다.
2. 우선 크기가 (N+1, M+1)인 배열을 하나 만들고, 모든 초깃값을 0으로 둔다.
3. 음식물이 떨어진 좌표의 값을 1로 수정한다.
4. 왼쪽 위에서 오른쪽 아래로 검사하면서, 값이 1인 경우 BFS를 진행한다.
   1. BFS를 진행하면서, 방문하는 좌표의 값을 0으로 수정한다.
   2. 현재 좌표 기준으로 상,하,좌,우 확인하여 값이 1인 경우 해당 좌표 큐에 저장(다음에 방문할 좌표)
   3. BFS를 종료할 때, 방문한 좌표의 수를 리턴하여 정답 갱신 (최댓값으로)

---

소스 코드

---

import sys
from collections import deque

input = lambda : sys.stdin.readline().rstrip()

N, M, K = map(int, input().split())

matrix = [[0] * (M+1) for _ in range(N+1)]

def bfs(matrix, x, y):
    count = 1
    matrix[x][y] = 0
    queue = deque([[x, y]])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx, ny = a + dx[i], b + dy[i]
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]) and \
               matrix[nx][ny] == 1:
                matrix[nx][ny] = 0
                count += 1
                queue.append([nx, ny])

    return count

for _ in range(K):
    a, b = map(int, input().split())
    matrix[a][b] = 1

answer = 0
for i in range(1, N+1):
    for j in range(1, M+1):
        if matrix[i][j] == 1:
            answer = max(answer, bfs(matrix, i, j))

print(answer)