[BOJ][python] 1743. 음식물 피하기

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

1743번: 음식물 피하기

---

💡IDEA

BFS를 사용하는 문제이다.

음식물이 있는 곳(1)과 없는 곳(0)을 구별하여 음식물이 있는 곳에서 BFS를 돌며 상하좌우로 연결된 음식물을 찾는다. 음식물을 찾으면 음식물이 없다고 갱신해주고, 개수를 센다. 이런식으로 하면 굳이 방문배열을 만들지 않고도 입력받은 맵 배열 하나로 해결된다.

BFS를 돌면서 음식물이 없어지기 때문에, 음식물이 있는 곳만 탐색하여 BFS를 수행하고 연결된 음식물의 개수를 최댓값으로 갱신시켜준다.

 

📌CODE

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

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def bfs(r, c):
    q = deque([(r, c)])
    maps[r][c] = 0
    cnt = 1
    while q:
        cr, cc = q.popleft()
        for k in range(4):
            nr = cr + dr[k]
            nc = cc + dc[k]
            if 0<nr<=N and 0<nc<=M and maps[nr][nc]:
                q.append((nr, nc))
                maps[nr][nc] = 0
                cnt += 1
    return cnt

N, M, K = map(int, input().split())
maps = [[0]*(M+1) for _ in range(N+1)]

for _ in range(K):
    a, b = map(int, input().split())
    maps[a][b] = 1
    
ans = 0
for r in range(1, N+1):
    for c in range(1, M+1):
        if maps[r][c]:
            ans = max(ans, bfs(r, c))
print(ans)